Idit Keidar
Sergio Rajsbaum
Skip Abstract Section
Abstract
We consider the consensus problem in an asynchronous model enriched with unreliable failure detectors and in the partial synchrony model. We consider algorithms that solve consensus and tolerate crash failures and/or message omissions. We prove tight lower bounds on the number of communication steps performed by such algorithms in failure-free executions. We present in a unified framework a number of related lower bound results. Thus, we shed light on the relationships among different known lower and upper bounds, and at the same time, illustrate a general technique for obtaining simple and elegant lower bound proofs. We also illustrate matching upper bounds: we algorithms that achieve the lower bound.
- M. K. Aguilera and S. Toueg. A simple bivalency-based proof that t-resilient consensus requires t + 1 rounds. Inf. Process. Lett., 71(3--4):155--158, 1999.]]Google Scholar
Cross Ref
- Z. Bar-Joseph and M. Ben-Or. A tight lower bound for randomized synchronous consensus. In ACM Symposium on Principles of Distributed Computing (PODC), pages 193--199, 1998.]] Google ScholarDigital Library
- P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, MA, 1987.]] Google ScholarDigital Library
- K. Birman, A. Schiper, and P. Stephenson. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst., 9(3):272--314, 1991.]] Google ScholarDigital Library
- T. D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. In ACM Symposium on Principles of Distributed Computing (PODC), pages 147--158, 1992.]] Google ScholarDigital Library
- T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225--267, Mar. 1996.]] Google ScholarDigital Library
- J. Chang and N. Maxemchunk. Reliable broadcast protocols. ACM Trans. Comput. Syst., 2(3), 1984.]] Google ScholarDigital Library
- B. Charron-Bost and A. Schiper. Uniform consensus is harder than consensus (extended abstract). Technical Report DSC/2000/028, Swiss Federal Institute of Technology, Lausanne, Switzerland, May 2000.]]Google Scholar
- F. Cristian and C. Fetzer. The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems, pages 642--657, June 1999.]] Google ScholarDigital Library
- D. Dolev, R. Reischuk, and H. R. Strong. Early stopping in byzantine agreement. J. ACM, 37(4):720--741, October 1990.]] Google ScholarDigital Library
- C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2):288--323, April 1988.]] Google ScholarDigital Library
- C. Dwork and D. Skeen. The inherent cost of nonblocking atomic commitment. In ACM Symposium on Principles of Distributed Computing (PODC), pages 1--11, 1983.]] Google ScholarDigital Library
- M. Fischer, N. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32:374--382, April 1985.]] Google ScholarDigital Library
- J. Gray. Notes on database operating systems. In Operating Systems: An Advanced Course, Lecture Notes in Computer Science, volume 60, pages 393--481. Springer Verlag, Berlin, 1978.]] Google ScholarDigital Library
- R. Guerraoui. Revisiting the relationship between non-blocking atomic commitment and consensus. In J.-M. Hélary and M. Raynal, editors, 9th International Workshop on Distributed Algorithms (WDAG), pages 87--100. Springer Verlag, September 1995. LNCS 972.]] Google ScholarDigital Library
- M. Hufrin and M. Raynal. A simple and fast asynchronous consensus protocol based on a weak failure detector. Distributed Computing, 12(4), 1999.]] Google ScholarDigital Library
- M. F. Kaashoek and A. S. Tanenbaum. Group communication in the Amoeba distributed operating system. In 11th International Conference on Distributed Computing Systems (ICDCS), pages 882--891, May 1991.]]Google ScholarCross Ref
- I. Keidar and D. Dolev. Efficient message ordering in dynamic networks. In 15th ACM Symposium on Principles of Distributed Computing (PODC), pages 68--76, May 1996.]] Google ScholarDigital Library
- L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133--169, May 1998. Also Research Report 49, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, September 1989.]] Google ScholarDigital Library
- L. Lamport. Lower bounds on consensus. Unpublished manuscript, March 2000.]]Google Scholar
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, July 78.]] Google ScholarDigital Library
- B. Lampson. How to build a highly available system using consensus. In Babaoglu and Marzullo, editors, Distributed Algorithms, LNCS 1151. Springer-Verlag, 1996.]] Google ScholarDigital Library
- Y. Moses and S. Rajsbaum. The unified structure of consensus: a layered analysis approach. In 17th ACM Symposium on Principles of Distributed Computing (PODC), pages 123--132. ACM, June 1998. submitted for journal publication.]] Google ScholarDigital Library
- A. Mostefaoui and M. Raynal. Solving consensus using chandra-toueg's unreliable failure detectors: a general approach. In 13th International Symposium on DIStributed Computing (DISC), Bratislava, Slovak Republic, 1999.]] Google ScholarDigital Library
- N. Santoro and P. Widmayer. Time is not a healer. In 6th Annual Symp. Theor. Aspects of Computer Science, volume 349 of LNCS, pages 304--313, Paderborn, Germany, Feb. 1989. Springer Verlag.]] Google ScholarDigital Library
- A. Schiper. Early consensus in an asynchronous system with a weak failure detector. Distributed Computing, 10(3):149--157, 1997.]] Google ScholarDigital Library
- F. B. Schneider. Implementing fault tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299--319, December 1990.]] Google ScholarDigital Library
- D. Skeen. Nonblocking commit protocols. In ACM SIGMOD International Symposium on Management of Data, pages 133--142, 1981.]] Google ScholarDigital Library
Index Terms
- On the cost of fault-tolerant consensus when there are no faults: preliminary version
Index terms have been assigned to the content through auto-classification.
Recommendations
Byzantine fault tolerant symmetric-persistent circle evacuation
AbstractWe consider ( n , f )-evacuation from a disk, a problem in which n > 1 robots, f of which are faulty, seek to evacuate through a hidden exit which is located on the perimeter of a unit disk.
We focus on symmetric-persistent ...
Highlights- Lower bound of 1 + 4 π n + 2 sin ( π 2 − π n ) for one faulty robot, even a crash-faulty one and almost matching upper bound of 3 + 4 π n.
Comments