Electrical computers and digital processing systems: multicomput – Distributed data processing
Reexamination Certificate
2004-11-23
2009-06-30
Nguyen, Quang N. (Department: 2441)
Electrical computers and digital processing systems: multicomput
Distributed data processing
C709S203000, C709S206000, C709S218000, C709S224000
Reexamination Certificate
active
07555516
ABSTRACT:
A distributed computing system can achieve consensus while introducing fewer message delays by using an algorithm that allows the constituent devices to vote on functions received directly from one or more clients. If a conflict occurs, a leader device from among the devices can be selected such that the leader device already knows of the other devices' previous votes, and can determine an appropriate function to propose, using an immediately subsequent proposal number, without performing the first phase of the Paxos algorithm. Alternatively, each device can independently determine, by using the same repeatable mechanism used by a leader device, what function the leader device would propose, and can then vote for that function using the immediately subsequent proposal number. If the devices' votes again result in a conflict, the Paxos algorithm can be used, or additional iterations can be performed prior to resorting to the Paxos algorithm.
REFERENCES:
patent: 5261085 (1993-11-01), Lamport
patent: 6105122 (2000-08-01), Muller et al.
patent: 6594698 (2003-07-01), Chow et al.
patent: 6671821 (2003-12-01), Castro et al.
patent: 6704887 (2004-03-01), Kwiat et al.
patent: 6957331 (2005-10-01), Kursawe et al.
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.
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 Systems16, 2, pp. 133-169, (May 1998). Also appeared as SRC Research Report 49.
Lamport, Leslie, Paxos Made Simple,ACM SIGACT News(Distributed Computing Column), 32,4 (Whole No. 121) pp. 18-25, Dec. 2001.
Lampson, Butler W.,The ABCD's of Paxos, Presented at Principles 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 the Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI '00), San Diego, USA, pp. 1-15, Oct. 2000.
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 ë(h -1)/3û-Resilient Consensus Protocol this paper was presented at theACM Symposium on Principles of Distributed Computing, pp. 154-162, 1984.
Keidar, Idit, et al., Moshe: A Group Membership Service for WANs to appear inACM Transactions on Computer Systems(TOCS), pp. 1-47; Aug. 2002.
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://theory.1cs.mit.edu/˜roger/Research/Papers /khazan-phd.pdf.
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).
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 of 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 Conference on System Sciences, vol. 3, pp. 317-326, Jan. 1998.
Malkhi, D. et al.; Secure and Scalable Replication in Phalanx;Proceedings of the 17th IEEE Symposium on Reliable Distributed Systems; p. 51-58, West Lafayette, Indiana, USA, Oct. 1998.
Malkhi, D. et al.; Byzantine Quorum Systems;Distributed Computing; vol. 11, No. 4, p. 203-213, 1998.
Goldberg, A. et al.; Towards an Archival Intermemory;International Forum on Research and Technology Advances in Digital Libraries; IEEE, pp. 147-156, 1998.
Hartman, J.H. et al.; The Swarm Scalable Storage System;19th ICDCS, pp. 74-81, 1999.
Guerraoui, Rachid et al.;Reducing the Cost for Non-Blocking in Atomic Commitment; Département d'Informatique, Ecole Polytechnique Fedérale de Lausanne, pp. 1-11, May 1996.
Hayashibara, Noahiro et al.;Performance Comparison Between the Paxos and Chandra-Toueg Consensus Algorithms; Département d'Informatique, Ecole Polytechnique Fedérale de Lausanne; Technical Report IC-2002-61, pp. 1-11, Aug. 2002.
Awerbuch, Baruch et al.;Maintaining Database Consistency in Peer to Peer Networks; Department of Computer Science, John Hopkins University; Technical Report CNDS-2002-1, pp. 1-14, Feb. 6, 2002.
Birrell, Andrew D. et al.;The Echo Distributed File System; Digital Equipment Corp. Systems Research Center; Technical Report 111, pp. 1-22, Sep. 10, 1993.
Liskov, Barbara et al.;Replication in the Harp File System; Proceedings of the 13thSymposium on Operating System Principles, 13 pp., Oct. 1991.
Hisgen, Andy et al.;New-Value Logging in the Ec
Microsoft Corporation
Nguyen Quang N.
Woodcock & Washburn LLP
LandOfFree
Fast Paxos recovery 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 Paxos recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Paxos recovery will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4114676