The proceedings contains 30 papers from the 17th annualacmsymposium on principles of distributedcomputing. Topics discussed include: compact routing schemes;reconsidering fragmentation;dynamic bandwidth allocations...
详细信息
The proceedings contains 30 papers from the 17th annualacmsymposium on principles of distributedcomputing. Topics discussed include: compact routing schemes;reconsidering fragmentation;dynamic bandwidth allocations;balancing networks resolved;asynchronous group mutual exclusions;SCRAMNet systems;private multiparty computations;database private information retrievals;fast-track multiparty computations;threshold cryptography;optimistic contract signing;asynchronous message-passing models;round-by-round fault detectors;message classification models;fault-tolerant concurrent programs;universal constructions;randomized synchronous consensus;and dynamic view-oriented group communication services.
We prove tight upper and lower bounds of Θ(t/√n log n) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, dynamic adversary. In particular this ...
详细信息
We prove tight upper and lower bounds of Θ(t/√n log n) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, dynamic adversary. In particular this proves that some restrictions are needed on the power of the adversary to allow randomized constant expected number of rounds protocols.
We propose a new system model for asynchronous distributed systems that we call the message classification model. Motivation for this model is its ability 1) to support a restricted but useful form of `communication b...
详细信息
We propose a new system model for asynchronous distributed systems that we call the message classification model. Motivation for this model is its ability 1) to support a restricted but useful form of `communication by time' by classifying messages as either `slow' or `fast' but without incorporating neither real-time clocks nor `time-outs', and 2) to describe transient and permanent network partitions. The message classification model allows the definition of different classes of classification schemes. To show that the model is indeed useful, we show how one can solve the consensus and the election problem for a certain class of message classification schemes.
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.
暂无评论