| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Fast Byzantine Consensus
July-September 2006 (vol. 3 no. 3)
pp. 202-215
We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps and number of processes for two--step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case. Further, we show a parameterized version of the protocol that is safe despite f Byzantine failures and, in the common case, guarantees two-step execution despite some number t of failures (t\le f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps and number of processes.
[1] R. Boichat, P. Dutta, S. Frolund, and R. Guerraoui, “Reconstructing Paxos,” SIGACT News, vol. 34, no. 2, pp. 42-57, 2003.
[2] M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” Proc. Symp. Operating Systems Design and Implementation (OSDI), 1999.
[3] M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance and Proactive Recovery,” ACM Trans. Computer Systems, vol. 20, no. 4, pp. 398-461, 2002.
[4] P. Dutta, R. Guerraoui, and M. Vukolić, “Best-Case Complexity of Asynchronous Byzantine Consensus,” Technical Report EPFL/IC/200499, École Polytechnique Fédérale de Lausanne, Feb. 2005.
[5] M. Fischer, N. Lynch, and M. Paterson, “Impossibility of Distributed Consensus with One Faulty Process,” J. ACM, vol. 32, no. 2, pp. 374-382, 1985.
[6] R. Friedman, A. Mostefaoui, and M. Raynal, “Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems,” IEEE Trans. Dependable and Secure Computing, vol. 2, no. 1, pp. 46-56, Jan. 2005.
[7] M. Hurfin and M. Raynal, “A Simple and Fast Asynchronous Consensus Protocol Based on a Weak Failure Detector,” Distributed Computing, vol. 12, no. 4, pp. 209-223, Sept. 1999.
[8] I. Keidar and S. Rajsbaum, “On the Cost of Fault-Tolerant Consensus when There Are No Faults,” Technical Report MIT-LCS-TR-821, Massachusetts Inst. of Technology, 2001.
[9] B. Kemme, F. Pedone, G. Alonso, A. Schiper, and M. Wiesmann, “Using Optimistic Atomic Broadcast in Transaction Processing Systems,” IEEE Trans. Knowledge and Data Eng., vol. 15, no. 4, pp. 1018-1032, July/Aug. 2003.
[10] K. Kursawe, “Optimistic Byzantine Agreement,” Proc. 21st IEEE Symp. Reliable Distributed Systems, pp. 262-267, Oct. 2002.
[11] L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Comm. ACM, vol. 21, no. 7, pp. 558-565, July 1978.
[12] L. Lamport, “The Part-Time Parliament,” ACM Trans. Computer Systems, vol. 16, no. 2, pp. 133-169, 1998.
[13] L. Lamport, “Lower Bounds for Asynchronous Consensus,” Proc. Int'l Workshop Future Directions in Distributed Computing, pp. 22-23, June 2002.
[14] L. Lamport, “Lower Bounds for Asynchronous Consensus,” Technical Report MSR-TR-2004-72, Microsoft Research, July 2004.
[15] L. Lamport, “Fast Paxos,” Technical Report MSR-TR-2005-112, Microsoft Research, 2005.
[16] L. Lamport and M. Fischer, “Byzantine Generals and Transaction Commit Protocols,” Technical Report 62, SRI Int'l, 1982.
[17] D. Malkhi and M. Reiter, “Byzantine Quorum Systems,” Distributed Computing, vol. 11, no. 4, pp. 203-213, 1998.
[18] J.-P. Martin and L. Alvisi, “Fast Byzantine Paxos,” Technical Report TR-04-07, Department of Computer Sciences, Univ. of Texas at Austin, Feb. 2004.
[19] J.-P. Martin, L. Alvisi, and M. Dahlin, “Minimal Byzantine Storage,” Proc. Sixth Int'l Conf. Distributed Computing (DISC), pp. 311-325, Oct. 2002.
[20] R. Rodrigues, M. Castro, and B. Liskov, “BASE: Using Abstraction to Improve Fault Tolerance,” Proc. 18th ACM Symp. Operating Systems Principles, pp. 15-28, Oct. 2001.
[21] A. Schiper, “Early Consensus in an Asynchronous System with a Weak Failure Detector,” Distributed Computing, vol. 10, no. 3, pp. 149-157, Apr. 1997.
[22] F.B. Schneider, “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial,” ACM Computing Surveys, vol. 22, no. 4, pp. 299-319, Sept. 1990.
[23] J. Yin, J.-P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin, “Separating Agreement from Execution for Byzantine Fault Tolerant Services,” Proc. 19th ACM Symp. Operating Systems Principles, pp. 253-267, Oct. 2003.
Index Terms:
Distributed systems, Byzantine fault tolerance, consensus.
Citation:
Jean-Philippe Martin, Lorenzo Alvisi, "Fast Byzantine Consensus," IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 3, pp. 202-215, July-Sept. 2006, doi:10.1109/TDSC.2006.35
