The proceedings contains 71 papers. Topics discussed include self stabilization algorithms, shared memory multiprocessors, message ordering, routing, random bit generators, random processes, real time object sharing, ...
详细信息
The proceedings contains 71 papers. Topics discussed include self stabilization algorithms, shared memory multiprocessors, message ordering, routing, random bit generators, random processes, real time object sharing, nonblocking and blocking algorithms, partitionable membership services, equivalence completions, and counting networks.
This paper studies the problem of making distributed decisions with the goal of maximizing a given utility function. The focus is entirely on the design and performance of the voting strategy and complete abstract fro...
详细信息
ISBN:
(纸本)9780897918008
This paper studies the problem of making distributed decisions with the goal of maximizing a given utility function. The focus is entirely on the design and performance of the voting strategy and complete abstract from implementational details, such as how ballots are collected from the voters and how the results of the election is communicated to the voters. The main interest is in giving a tight estimate of the cumulative profit achievable in a worst-case setting.
Analytical models for the realistic setting where old load information is available are developed. The models are based on considering the behavior of limiting systems where the number of processors goes to infinity. ...
详细信息
Analytical models for the realistic setting where old load information is available are developed. The models are based on considering the behavior of limiting systems where the number of processors goes to infinity. The studies of specific models demonstrate the importance of using randomness to break symmetry in the systems and yield important rules of thumb for system design.
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that w...
详细信息
ISBN:
(纸本)9781581138023
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.
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.
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementati...
详细信息
ISBN:
(纸本)9781581138023
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t
This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unify...
详细信息
ISBN:
(纸本)9781581134858
This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault detectors. We show that any P-based t-resilient consensus algorithm requires at least t+2 rounds for a global decision even in runs that are synchronous. We then prove the bound to be tight by exhibiting a new P-based t-resilient consensus algorithm that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we knew of (which requires 2t + rounds). We contrast our lower bound with the well-known t + 1 round tight lower bound on consensus for the synchronous model, pointing out the price of indulgence.
暂无评论