Fast byzantine paxos

Details Fast byzantine paxos Fast byzantine paxos

2002-08-15

2009-11-17

Flynn, Nathan J (Department: 2454)

Electrical computers and digital processing systems: multicomput

Distributed data processing

C709S202000, C709S248000

Reexamination Certificate

active

07620680

ABSTRACT:
A distributed computing system can operate in the face of malicious failures on the part of some of its constituent devices, and provide a minimum of message delays between receiving a client request and providing a response, when each device within the system verifies the sender of any message it receives, and the propriety of the message. The sender can be verified through message authentication schemes or digital signature schemes. The propriety of a message can be verified by receiving a sufficiently large number of equivalent, properly authenticated messages. If the number of malicious devices is represented by the variable “M”, a sufficient number of equivalent, properly authenticated messages to verify that the message is true can be any number of messages greater than M. Furthermore, to verify that a leader device is not maliciously submitting different proposals to different devices using the same proposal number, a quorum of devices can be required to select a proposal, where a quorum is a sufficiently large number of devices such that any other quorum has, as a majority of its devices, non-malicious devices from the first quorum. Therefore, the distributed computing system can operate properly with M number of malicious failures and F number of total failures, and with a minimum of message delays, if the number of constituent devices in the distributed computing system is greater than 3F+2M. Additionally, if the distributed computing system can revert to a more traditional algorithm if too many devices fail or become malicious, it can use a message-delay-reducing algorithm while having as few as 2Q+F+2M+1 constituent devices, where Q is the number of devices that can fail and still allow the system to use a message-delay-reducing algorithm.

REFERENCES:
patent: 5261085 (1993-11-01), Lamport
patent: 6202067 (2001-03-01), Blood et al.
patent: 6216150 (2001-04-01), Badovinatz et al.
patent: 6351811 (2002-02-01), Groshon et al.
patent: 6567927 (2003-05-01), Brinkmann
patent: 6587860 (2003-07-01), Chandra et al.
patent: 6671821 (2003-12-01), Castro et al.
patent: 6704887 (2004-03-01), Kwiat et al.
patent: 6754845 (2004-06-01), Kursawe et al.
patent: 6826601 (2004-11-01), Jacobs et al.
patent: 6931431 (2005-08-01), Cachin et al.
patent: 2001/0025351 (2001-09-01), Kursawe et al.
patent: 2002/0116611 (2002-08-01), Zhou et al.
patent: 2009/0089358 (2009-04-01), Beckwith et al.
Anceaume et al., “Converging Toward Decision Conditions”6thInternational Conference on Principles of Distributed Systems, France, pp. 53-63 (Dec. 11-13, 2002).
Mostefaoui et al., “IRISA Research Report No. 1355” (Oct. 2000).
Brasileiro et al., “IRISA Research Report No. 1321” (Apr. 2000).
Keidar, Idit, et al.; On the Cost of Fault-Tolerant Consensus When There Are No Faults—A Tutorial; SIGACT News 32(2), Distributed Computing column, pp. 45-63; Jun. 2001.
Dwork, Cynthia, et al.; Consensus in the Presence Of Partial Synchrony;Journal of the ACM, 35(2):288-323, Apr. 1988.
Lampson, Butler W.; How to Build a Highly Available System Using Consensus; http://www.research.microsoft.com.
Lamport, Leslie; The Implementation of Reliable Distributed Multiprocess Systems;Computer Networks, 2:95-114,1978.
Lamport, Leslie, et al.; The Byzantine Generals Problem; ACM Transactions on Programming Languages and Systems, vol. 4, No. 3, Jul. 1982, pp. 382-401.
Brasileiro et al, “Consensus in One Communication Step”, IRISA, Universite de Rennes 1, France, 9 pages.
Lamport, Leslie, “Time, Clocks, and the Ordering of Events in a Distributed System”,Communication of the ACM, 21(7):558-565, Jul. 1978.
Lamport, Leslie, “The Part-Time Parliament”,ACM Transactions on Computer Systems 16, 2 (May 1998), pp. 133-169. Also appeared as SRC Research Report 49.
Lamport, Leslie, “Paxos Made Simple”,ACM SIGACTNews (Distributed Computing Column), 32,4 (Whole No. 121, Dec. 2001) pp. 18-25.
Lampson, Butler W., “The ABCD's of Paxos”, Presented atPrinciples of Distributed Computing, 2001, as one of the papers celebrating Leslie Lamport's 60thBirthday, retrieved from http://research .microsoft.com/lampson/65-ABCDPaxos/Acrobat.pdf.
Castro, Miguel, et al., “Practical Byzantine Fault Tolerance”, appears inProceedings of the Third-Symposium on Operating Design and Implementation, New Orleans, USA, Feb. 1999, pp. 1-14.
Castro, Miguel, et al., “Proactive Recovery in a Byzantine-Fault-Tolerant System”, appears in theProceedings of the Fourth Symposium on Operating Systems Design and Implementation(OSDI '00), San Diego, USA, Oct. 2000, pp. 1-15.
Huang, Yennun, et al., “Software Rejuvenation: Analysis, Module and Applications”,Proc. International Symposium on Fault Tolerant Computing, pp. 381-390, (1995).
Bracha, Gabriel, “An asynchronous └(η -1)/3┘-resilient consensus protocol” this paper was presented at theACM Symposium on Principles of Distributed Computing1984, pp. 154-162.
Keidar, Idit, et al., “Moshe: A Group Membership Service for WANs” to appear inACM Transactions on Computer Systems(TOCS), Aug. 2002, pp. 1-47.
Khazan, Roger, I., “A One-Round Algorithm for Virtually Synchronous Group Communication in Wide Area Networks”, PH.D. dissertation, Department of Electrical Engineering and Computer Science. MIT., May 22, 2002. Thesis Supervisors: Prof. Nancy A. Lynch and Dr. Idit Keidar. Retrieved from http://theroy.1cs.mit.edu/˜ roger/Research/Papers /khazan-phd.pdf.
Schneider, F.; Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial;Computing Surveys, 22(3):299-319, Sep. 1990.
Deswarte, Y. et al; Intrusion Tolerance in Distributed Computing Systems;Proceedings of the 1991 IEEE Symposium on Research in Security and Privacy; pp. 110-121, May 1991.
Canetti, R. et al.; Fast asynchronous Byzantine agreement with optimal resilience;Proc. 25th Annual ACM Symposium on Theory of Computing(STOC), pp. 42-51, 1993.
Reiter, M; How to Securely Replicate Services;ACM Transactions on Programming Languages and Systems, vol. 16, No. 3, pp. 986-1009, May 1994.
Reiter, M. K.; Secure Agreement Protocols: Reliable and Atomic Group Multicast in Rampart;Proceedings of the 2nd ACM Conference on Computer and Communications Security, pp. 68-80, Fairfax, Virginia, Nov. 1994.
Gong, L. et al.; Byzantine Agreement With Authentication: Observations and Applications in Tolerating Hybrid and Link Faults;Dependable Computing for Critical Applications—5, pp. 79-90, IFIP WG 10.4, preliminary proceedings, 1995.
Reiter, M. K.; The Rampart toolkit for building high-integrity services;Theory and Practice in Distributed Systems, International Workshop, Selected Papers, Lecture Notes in Computer Science, vol. 938, K. P. Birman, F. Mattern, and A. Schiper, Eds., Springer-Verlag, Berlin, 99-110, 1995.
Reiter, M. K.; Distributing Trust With the Rampart Toolkit;Communications of the ACM; 39, 4 pp. 71-74, Apr. 1996.
Malkhi, D. et al.; A High-Throughput Secure Reliable Multicast Protocol;Proceedings of the 9th Computer Security Foundations Workshop, Kenmore, Ireland, pp. 9-17, Jun. 1996.
Malkhi, D. et al.; A High-Throughput Secure Reliable Multicast Protocol;Journal of Computer Security. Also inProceedings of the 9thIEEE Computer Security Foundations Workshop, pp. 9-17, Jun. 1996.
Malkhi, D. et al.; Byzantine Quorum Systems;Proceedings of the 29th ACM Symposium on Theory of Computing, May 1997.
Malkhi, D. et al.; The Load and Availability of Byzantine Quorum Systems;Proceedings 16thACM Symposium on Principles of Distributed Computing(PODC), pp. 249-257, Aug. 1997.
Kihlstrom, K. P. et al.; Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector;Proceedings of the International Conference on Principles of Distributed Systems(OPODIS'97), Hermes, Chantilly, France, 61-76, 1997.
Kihlstrom, K. P. et al.; The SecureRing Protocols for Securing Group Communication;Proceedings of the 31st Hawaii International Con

Affiliated with

Also associated with

Rating

Fast byzantine paxos does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast byzantine paxos, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast byzantine paxos will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4129228