Timeliness, failure-detectors, and consensus performance

ABSTRACT

We study the implication that various timeliness and failure detector assumptions have on the performance of consensus algorithms that exploit them. We present a general framework, GIRAF, for expressing such assumptions, and reasoning about the performance of indulgent algorithms.

REFERENCES

• 1: Marcos Kawazoe Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Stable Leader Election, Proceedings of the 15th International Conference on Distributed Computing, p.108-122, October 03-05, 2001
• 2: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, On implementing omega with weak reliability and synchrony assumptions, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.306-314, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872081]
• 3: 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 [doi>10.1145/1011767.1011816]
• 4: O. Bakr. Performance evaluation of distributed algorithms over the Internet. Master's thesis, MIT, Feb. 03.
• 5: Omar Bakr , Idit Keidar, Evaluating the running time of a communication round over the internet, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571864]
• 6: Francisco V. Brasileiro , Fabíola Greve , Achour Mostéfaoui , Michel Raynal, Consensus in One Communication Step, Proceedings of the 6th International Conference on Parallel Computing Technologies, p.42-50, September 03-07, 2001
• 7: N. Cardwell, S. Savage, and T. Anderson. Modeling the performance of short tcp connections, 1998.
• 8: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 9: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 10: Bernadette Charron-Bost , André Schiper, Uniform consensus is harder than consensus, Journal of Algorithms, v.51 n.1, p.15-37, 1 April 2004 [doi>10.1016/j.jalgor.2003.11.001]
• 11: Flaviu Cristian , Christof Fetzer, The Timed Asynchronous Distributed System Model, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.642-657, June 1999 [doi>10.1109/71.774912 ]
• 12: P. Dutha, R. Guerraoui, and I. Keidar. The overhead of consensus failure recovery. Technical Report 200456, École Polytechnique Fédérale de Lausanne, 2004.
• 13: P. Dutha, R. Guerraoui, and I. Keidar. The overhead of consensus failure recovery. Submitted for publication, 2005.
• 14: Partha Dutta , Rachid Guerraoui, Fast Indulgent Consensus with Zero Degradation, Proceedings of the 4th European Dependable Computing Conference on Dependable Computing, p.191-208, October 23-25, 2002
• 15: Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571838]
• 16: How Fast Can Eventual Synchrony Lead to Consensus?, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.22-27, June 28-July 01, 2005 [doi>10.1109/DSN.2005.54]
• 17: P. Dutta, R. Guerraoui, and B. Pochon. Tight lower bounds on early local decisions in uniform consensus. In DISC, pages 264--278, Oct 2003.
• 18: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 19: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 20: Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.143-152, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277724]
• 21: Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343630]
• 22: Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004 [doi>10.1109/TC.2004.1268403]
• 23: Rachid Guerraoui , André Schiper, "Gamma-Accurate" Failure Detectors, Proceedings of the 10th International Workshop on Distributed Algorithms, p.269-286, October 09-11, 1996
• 24: I. Keidar and S. Rajsbaum. On the cost of fault-tolerant consensus when there are no faults - a tutorial. Technical Report MIT-LCS-TR-821, MIT, May 2001.
• 25: I. Keidar and A. Shraer. How to choose a timing model? Technical Report CCIT 586, Department of Electrical Engineering, Technion, May 2006.
• 26: I. Keidar and A. Shraer. Timeliness, failure-detectors, and consensus performance. Technical Report CCIT 576, Department of Electrical Engineering, Technion, Feb. 2006.
• 27: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 28: N. Lynch and M. Tuttle. An introduction to Input/Output Automata. CWI Quarterly, 2(3):219--246, 1989.
• 29: D. Malkhi, F. Oprea, and L. Zhou. Omega meets paxos: Leader election and stability without eventual timely links. DISC, pages 199--213, sep 2005.
• 30: Jean-Philippe Martin, Fast Byzantine Consensus, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.402-411, June 28-July 01, 2005 [doi>10.1109/DSN.2005.48]
• 31: Achour Mostéfaoui , Michel Raynal, Solving Consensus Using Chandra-Toueg's Unreliable Failure Detectors: A General Quorum-Based Approach, Proceedings of the 13th International Symposium on Distributed Computing, p.49-63, September 27-29, 1999
• 32: Nicola Santoro , Peter Widmayer, Time is Not a Healer, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science, p.304-313, February 16-18, 1989
• 33: U. Schmid and C. Fetzer. Randomized asynchronous consensus with imperfect communications. SRDS, 00:361, 2003.
• 34: U. Schmid and B. Weiss. Impossibility results and lower bounds for consensus under link failures. Technical Report 183/1-129, Technische Universita"t Wien, Dept. of Automation, Apr. 2002.
• 35: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
eventual synchrony, failure detectors, indulgent consensus, lower bounds