A wait-free universal construction is attractive because, no matter what type of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the approp...
详细信息
A wait-free universal construction is attractive because, no matter what type of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the appropriate types. However, the worst-case time complexity of every existing n-process universal construction is Ω(n): that is, in any implementation obtained by instantiating a universal construction, in the worst-case a process performs Ω(n) computation in order to complete a single operation on the implemented object. In fact, a lower bound of Ω(n) has been proved for the worst-case local time complexity of any oblivious universal construction.
作者：
Abadi, M.InterTrust
Strategic Technologies and Architectural Research Lab.
Since the 1970s, Leslie Lamport has done substantial work on specification and verification methods. This work might be regarded as complementary to his other celebrated research on concurrency and distributed computi...
详细信息
ISBN:
(纸本)9781581133837
Since the 1970s, Leslie Lamport has done substantial work on specification and verification methods. This work might be regarded as complementary to his other celebrated research on concurrency and distributedcomputing, perhaps sometimes even as secondary. However, this work is excellent in its own right. It introduces (or distills) many original and useful ideas. These include the important definitions of safety and liveness properties, and later the insightful conception of a temporal logic of actions. This talk will describe some of Lamport's ideas and results on specification and verification methods. It will touch on the impact of some of those ideas on the speaker (who collaborated closely with Lamport for several years) and on the field.
A certificate for the k connectivity of a graph G = (V, E) is a subset E′ of E such that (V, E′) is k connected iff G is k connected. Let n = |V| and m = |E|. A certificate is called sparse if it has size O(kn). We ...
详细信息
ISBN:
(纸本)9780897917100
A certificate for the k connectivity of a graph G = (V, E) is a subset E′ of E such that (V, E′) is k connected iff G is k connected. Let n = |V| and m = |E|. A certificate is called sparse if it has size O(kn). We present a distributed algorithm for computing sparse certificate for k connectivity whose time complexity is O(k(D + n0.614)) where D is the diameter of the network. A new algorithm for identifying biconnected components is also presented. This algorithm is significantly simpler than many existing algorithms and can be implemented in distributed environment to run in O(D + n0.614) time. Both algorithms improve on the previous best known time bounds. Our main focus in this paper is the time complexity. However, no more than a polynomial number of messages, each of size O(log n), are generated by the algorithm.
We present a mix network that achieves efficient integration of public-key and symmetric-key operations. This hybrid mix network is capable of natural processing of arbitrarily long input elements, and is fast in both...
详细信息
ISBN:
(纸本)9781581133837
We present a mix network that achieves efficient integration of public-key and symmetric-key operations. This hybrid mix network is capable of natural processing of arbitrarily long input elements, and is fast in both practical and asymptotic senses. While the overhead in the size of input elements is linear in the number of mix servers, it is quite small in practice. In contrast to previous hybrid constructions, ours has optimal robustness, that is, robustness against any minority coalition of malicious servers.
The proceedings contain 59 papers. The topics discussed include: node and edge averaged complexities of local graph problems;overcoming congestion in distributed coloring;the landscape of distributed complexities on t...
ISBN:
(纸本)9781450392624
The proceedings contain 59 papers. The topics discussed include: node and edge averaged complexities of local graph problems;overcoming congestion in distributed coloring;the landscape of distributed complexities on trees and beyond;brief announcement: on polynomial-time local decision;brief announcement: distributed MST computation in the sleeping model: awake-optimal algorithms and lower bounds;brief announcement: broadcasting time in dynamic rooted trees is linear;a recursive early-stopping phase king protocol;optimal synchronous approximate agreement with asynchronous fallback;perfectly-secure synchronous MPC with asynchronous fallback guarantees;brief announcement: asynchronous randomness and consensus without trusted setup;and brief announcement: deterministic consensus and checkpointing with crashes: time and communication efficiency.
This brief announcement introduces the family of generalized symmetry breaking (GSB) tasks, that includes election, renaming and many other symmetry breaking tasks. Differently from agreement tasks, a GSB task is &quo...
详细信息
The global record notion is of importance in asynchronous parallel or distributed systems. Informally, a local record is a local state selected by a process and a global recored is a set of local records, one from eac...
详细信息
The global record notion is of importance in asynchronous parallel or distributed systems. Informally, a local record is a local state selected by a process and a global recored is a set of local records, one from each process of the system. This paper aims to provide an answer to the question whether or not local records could belong to a consistent global record of the computation, given a subset of local records. Firstly, it considers a very general computational model that encompasses shared memory, reliable point-to-point communication, multicast communication and unreliable communication systems. Secondly, it introduces a formal frame based on the notion of record interval and on a precedence relation defined on them. Within this general model and frame, a necessary and sufficient condition that answers the question is proved.
Consider a distributed systems S of sensors, where the goal is to continuously output an agreed reading. The input readings of non-faulty sensors may changed over time;and some of the sensors may be faulty (Byzantine)...
详细信息
ISBN:
(纸本)9781595939890
Consider a distributed systems S of sensors, where the goal is to continuously output an agreed reading. The input readings of non-faulty sensors may changed over time;and some of the sensors may be faulty (Byzantine). Thus, the system is required to repeatedly perform consensus oil the input values. This paper investigates the following question: assuming. the input, values of all the non-faulty sensors remain unchanged for a long period of time, what can be said,about the agreed-upon output reading of the entire system. We prove that no system's output is stable, i.e. the faulty sensors call force a change of the output value at least once. We show that any system with binary input values can avoid changing its output, more than once, thus matching the lower bound. For systems with multi-value inputs, we show that, the output may change at most twice;when n = 3f + 1 this solution is shown to be tight. Moreover, the solutions we Present, are self-stabilizing.
A network consists of a set of processors and a set of communication links connecting pairs of processors. In the past, dozens of papers have been written on the subject of efficient distributed algorithms for various...
详细信息
暂无评论