|
 ABSTRACT
Reaching agreement is a primitive of distributed computing. Whereas this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: A system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer et al. have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper their work is extended: Several critical system parameters, including various synchrony conditions, are identified and how varying these affects the number of faults that can be tolerated is examined. The proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
AGHILI, H., ASTRAHAN, M., FINKELSTEIN, S., KIM, W., MCPHERSON, J., SCHKOLNICK, M., AND STRONG, R. A prototype for a highly available database system. Rep. RJ 3755, IBM Research Division, San Jose, Calif., 1983.
|
 |
2
|
Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada
[doi> 10.1145/800222.806740]
|
| |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
DOLEV, D., AND STRONG, H. R. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12 (1983), 656-666.
|
| |
8
|
DOLEV, D., REISCHUK, R., AND STRONG, H.R. Eventual is earlier than immediate. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (Chicago, I11., Nov. 3-5). IEEE, New York, 1982, pp. 196-203.
|
| |
9
|
DWORK, C., LYNCH, L., AND STOCKMEYER, L. Consensus in the presence of partial synchrony. IBM Res. Rep. RJ 4892, IBM Research Division, San Jose, Calif., Oct. 1985.
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
RAmN, M.O. Randomized Byzantine generals. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Tucson, Ariz., Nov. 7-9). IEEE, New York, pp. 403-409.
|
| |
14
|
|
CITED BY 118
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Danny Dolev , Eli Gafni , Nir Shavit, Toward a non-atomic era: l-exclusion as a test case, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.78-92, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ajei Gopal , Ray Strong , Sam Toueg , Flaviu Cristian, Early-delivery atomic broadcast, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.297-309, August 22-24, 1990, Quebec City, Quebec, Canada
|
|
|
Rajeev Alur , Hagit Attiya , Gadi Taubenfeld, Time-adaptive algorithms for synchronization, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.800-809, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.147-158, August 10-12, 1992, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tushar Chandra , Vassos Hadzilacos , Prasad Jayanti , Sam Toueg, Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.334-343, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.359-369, May 05-08, 1991, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.354-362, August 14-17, 1994, Los Angeles, California, United States
|
|
|
Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kouznetsov, Synchronizing without locks is inherently expensive, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chunyang Ye , S. C. Cheung , W. K. Chan , Chang Xu, Local analysis of atomicity sphere for B2B collaboration, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Prasant Gopal Anumanchipalli , Anuj Gupta , Pranav K. Vasishta , Piyush Bansal , Kannan Srinathan, Brief announcement: global consistency can be easier than point-to-point communication, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
|
REVIEW
"Greg Speegle : Reviewer"
Reaching agreement in the presence of failures by a distributed system is an
interesting problem. This paper defines the conditions that are sufficient
for agreement to occur and some conditions that make agreement impossible.
The paper identifi
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2