Computer Science – Data Structures and Algorithms
Scientific paper
2002-09-06
Computer Science
Data Structures and Algorithms
29 pages; survey paper written for PODC 20th anniversary issue of Distributed Computing
Scientific paper
The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single process can fail. Since its publication, two decades of work on fault-tolerant asynchronous consensus algorithms have evaded this impossibility result by using extended models that provide (a) randomization, (b) additional timing assumptions, (c) failure detectors, or (d) stronger synchronization mechanisms than are available in the basic model. Concentrating on the first of these approaches, we illustrate the history and structure of randomized asynchronous consensus protocols by giving detailed descriptions of several such protocols.
No associations
LandOfFree
Randomized protocols for asynchronous consensus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Randomized protocols for asynchronous consensus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized protocols for asynchronous consensus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-669838