Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Consensus is a central problem of fault-tolerant distributed computing that, in the context of synchronous distributed systems, has received a lot of attention in the crash failure model and in the Byzantine failure model. This paper considers synchronous distributed systems made up of n processes, where up to t can commit failures by crashing or omitting to send or receive messages when they should ("process omission" failure model). It presents a protocol solving uniform consensus in such a context. This protocol has several noteworthy features. First, it is particularly simple. Then, it is optimal both in (1) the number of communication steps needed for processes to decide and stop, namely, min(f+2,t+1) where f is the actual number of faulty processes, and (2) the number of processes that can be faulty, namely t<n/2. Moreover, (3) it ensures that no process (be it correct or faulty) executes more than min(f+2,t+1) rounds, thereby extending the decision lower bound to the full completion time. The design of a uniform consensus protocol with such optimality requirements was an open problem. Interestingly, as min(f+2,t+1) is a lower bound to solve uniform consensus in the synchronous crash failure model, the proposed protocol shows that uniform consensus is not "harder'' in the omission failure model than in the crash failure model. The protocol is also message size efficient as, in addition to values, a message has to piggyback only n bits of control information.

REFERENCES

• 1: Aguilera M.K. and Toueg S., A Simple Bivalency Proof that t-Resilient Consensus Requires t + 1 Rounds. Information Processing Letters, 71:155--178, 1999.
• 2: Piotr Berman , Juan A. Garay , Kenneth J. Perry, Optimal Early Stopping in Distributed Consensus (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.221-237, November 02-04, 1992
• 3: Charron-Bost B. and Schiper A., Uniform Consensus is Harder than Consensus (Extended Abstract). Technical Report DSC/2000/028, EPFL, May 2000.
• 4: Danny Dolev , Ruediger Reischuk , H. Raymond Strong, Early stopping in Byzantine agreement, Journal of the ACM (JACM), v.37 n.4, p.720-741, Oct. 1990 [doi>10.1145/96559.96565]
• 5: Dolev D. and Strong R., Authenticated Algorithms for Byzantine Agreement. Siam Journal of Computing, 12:656--666, 1983.
• 6: Cynthia Dwork , Yoram Moses, Knowledge and common knowledge in a byzantine environment: crash failures, Information and Computation, v.88 n.2, p.156-186, Oct. 1990 [doi>10.1016/0890-5401(90)90014-9]
• 7: Fischer M.J. and Lynch N., A Lower Bound for the Time to Assure Interactive Consistency. Information Processing Letters, 71:183--186, 1982.
• 8: 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]
• 9: Juan A. Garay , Yoram Moses, Fully Polynomial Byzantine Agreement for Processors in Rounds, SIAM Journal on Computing, v.27 n.1, p.247-290, Feb. 1998 [doi>10.1137/S0097539794265232]
• 10: Vijay K. Garg, Ph.D., Elements of distributed computing, John Wiley & Sons, Inc., New York, NY, 2002
• 11: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 12: Idit Keidar , Sergio Rajsbaum, A simple proof of the uniform consensus synchronous lower bound, Information Processing Letters, v.85 n.1, p.47-52, 16 January 2003 [doi>10.1016/S0020-0190(02)00333-2]
• 13: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 14: Le Fessant F., The complexity of Early-Deciding in Unreliable Synchronous Networks. Research Report #TR-2003-23, Microsoft Research, Cambridge (UK), 2003.
• 15: Fabrice Le Fessant , Philippe Raipin Parvédy , Michel Raynal, Brief announcement: early decision despite general process omission failures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.222-222, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872068]
• 16: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: Gil Neiger , Sam Toueg, Automatically increasing the fault-tolerance of distributed algorithms, Journal of Algorithms, v.11 n.3, p.374-419, Sep. 1990 [doi>10.1016/0196-6774(90)90019-B]
• 18: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 19: K J Perry , S Toueg, Distributed agreement in the presence of processor and communication faults, IEEE Transactions on Software Engineering, v.12 n.3, p.477-482, March 1986
• 20: Philippe Raipin Parvedy , Michel Raynal, Uniform Agreement Despite Process Omission Failures, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.212.2, April 22-26, 2003
• 21: Raïpin Parvédy Ph. and Raynal M., Optimal Early-stopping Uniform Consensus in Synchronous Systems with Process Omission Failures. Research Report #1509, University of Rennes (France), January 2003.
• 22: Michel Raynal, Consensus in Synchronous Systems: A Concise Guided Tour, Proceedings of the 2002 Pacific Rim International Symposium on Dependable Computing, p.221, December 16-18, 2002
• 23: Marcel-Cătălin Roşu, Early-stopping Terminating Reliable Broadcast protocol for general-omission failures, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.209, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248092]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
consensus, crash failure, omission failure, round-based computation, send omission, send/receive omission, synchronous distributed system, uniform consensus