Tight bounds for asynchronous randomized consensus

ABSTRACT

A distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes.

This work proves that the total step complexity of randomized consensus is Θ(n²) in an asynchronous shared memory systemusing multi-writer multi-reader registers. The bound is achieved by improving both the lower and the upper bounds for this problem.

In addition to improving upon the best previously known result bya factor of log² n, the lower bound features agreatly streamlined proof. Both goals are achieved through restricting attention to a set of layered executions andusing an isoperimetric inequality for analyzing their behavior.

The matching algorithm decreases the expected total step complexity by a log n factor, by leveraging themulti-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithmas a stochastic process and applying Kolmogorov's inequality.

REFERENCES

• 1: Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
• 2: James Aspnes, Time-and space-efficient randomized consensus, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.325-331, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93433]
• 3: James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998 [doi>10.1145/278298.278304]
• 4: James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003 [doi>10.1007/s00446-002-0081-5]
• 5: James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
• 6: James Aspnes , Orli Waarts, Randomized Consensus in Expected O(n log^ 2 n) Operations Per Processor, SIAM Journal on Computing, v.25 n.5, p.1024-1044, Oct. 1996 [doi>10.1137/S0097539792240881]
• 7: H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
• 8: Hagit Attiya , Jennifer Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
• 9: Yonatan Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.209-218, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259441]
• 10: Yonatan Aumann , Michael A. Bender, Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler, Distributed Computing, v.17 n.3, p.191-207, March 2005 [doi>10.1007/s00446-004-0113-4]
• 11: Yonatan Aumann , Avivit Kapah-Levy, Cooperative sharing and asynchronous consensus using single-reader single-writer registers, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.61-70, January 17-19, 1999, Baltimore, Maryland, United States
• 12: Ziv Bar-Joseph , Michael Ben-Or, A tight lower bound for randomized synchronous consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.193-199, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277733]
• 13: Gabriel Bracha , Ophir Rachman, Randomized Consensus in Expected O(n²log n) Operations, Proceedings of the 5th International Workshop on Distributed Algorithms, p.143-150, October 07-09, 1991
• 14: Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248083]
• 15: Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
• 16: [16] D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM J. Comput., 12(4):656-666, 1983.
• 17: [17] W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. John Wiley & Sons, 3rd edition, 1968.
• 18: [18] W. Feller. An Introduction to Probability Theory and Its Applications, volume 2. John Wiley & Sons, 2nd edition, 1971.
• 19: [19] M. J. Fischer and N. A. Lynch. A lower bound for the time to assure interactive consistency. Inf. Process. Lett., 14(4):183-186, 1982.
• 20: 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]
• 21: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 22: 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]
• 23: [23] M. C. Loui and H. H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, pp. 163-183, 1987.
• 24: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 25: Yoram Moses , Sergio Rajsbaum, The unified structure of consensus: a layered analysis approach, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.123-132, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277720]
• 26: 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
• 27: [27] G. Schechtman. Levy type inequality for a class of finitie metric spaces. In Lecture Notes in Mathematics: Martingle Theory in Harmonic Analysis and Banach Spaces, volume 939, pp. 211-215. Springer-Verlag, 1981.
• 28: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Algorithms, Theory

Keywords:
distributed computing, isoperimetric inequality, lower bound, randomized algorithms, shared-memory