Electrical computers and digital processing systems: multicomput – Computer-to-computer session/connection establishing
Reexamination Certificate
2004-06-18
2010-12-21
Follansbee, John (Department: 2451)
Electrical computers and digital processing systems: multicomput
Computer-to-computer session/connection establishing
C709S203000, C709S205000
Reexamination Certificate
active
07856502
ABSTRACT:
A distributed computing system can be operated in a fault tolerant manner using a collection of auxiliary computing devices and more main computing devices than the number of faults the system can tolerate. A quorum of all of the main computing devices can be used. In the event of a failure, an alternative quorum from a selected set of quorums, comprising at least one main computing device and some or all of the auxiliary computing devices, can be used to complete pending operations and to select a new set of quorums. Alternatively, another state machine, comprising at least one main computing device and some or all of the auxiliary computing devices, can select a new quorum comprising the currently operating main computing devices, and the new quorum can then complete pending operations and can continue to select proposals using the proposal number assigned by the other state machine.
REFERENCES:
patent: 5261085 (1993-11-01), Lamport
patent: 6067655 (2000-05-01), Kovacs et al.
patent: 6108699 (2000-08-01), Moiin
patent: 6182133 (2001-01-01), Horvitz
patent: 6192401 (2001-02-01), Modiri et al.
patent: 6519697 (2003-02-01), Denman et al.
patent: 6671821 (2003-12-01), Castro et al.
patent: 7334154 (2008-02-01), Lorch et al.
patent: 7392302 (2008-06-01), Halpern
patent: 7454521 (2008-11-01), Howell et al.
patent: 7555516 (2009-06-01), Lamport
patent: 7558883 (2009-07-01), Lamport
patent: 7565433 (2009-07-01), Lamport
patent: 7620680 (2009-11-01), Lamport
patent: 2003/0023680 (2003-01-01), Shirriff
patent: 2003/0065708 (2003-04-01), Jacobs et al.
patent: 2003/0158908 (2003-08-01), Jacobs et al.
patent: 2003/0233433 (2003-12-01), Halpern
patent: 2005/0149609 (2005-07-01), Lamport
patent: 2005/0198106 (2005-09-01), Lamport
patent: 2005/0283373 (2005-12-01), Lamport
patent: 2006/0136781 (2006-06-01), Lamport
Rajsbaum, Sergio “Deconstructing Paxos” Mar. 2003, ACM SIGACT News, vol. 34, No. I, pp. 47-67.
Englert, Burkhard and Gafni, Eli “Fast Collect in the absence of contention” IEEE, Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS'02), Jul. 2-5, 2002, pp. 537-543.
Neilsen, M-L., “A dynamic probe strategy for quorum systems,” Proceedings of 17th International Conference on Distributed Computing Systems, IEEE, May 27-30, 1997, 2 pages, Abstract only.
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.
Gafni, E. et al., “Disk Paxos”,Distributed Computing, 2003, 16(1), 1-20, XP-002362227.
Rajsbaum, S., “ACM SIGACT News Distributed Computing Column 10”, Deconstructing Paxos,ACM SIGACT News, Mar. 2003, 34(1), 47-67, XP-002358967.
Rajsbaum, S., “ACM SIGACT News Distributed Computing Column 11”, Reconstructing Paxos,ACM SIGACT News, Jun. 2003, 34(2), 42-57, XP-002358966.
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 (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.
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 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 o
Lamport Leslie B.
Massa Michael T.
Follansbee John
Mejia Anthony
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Cheap 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 Cheap paxos, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cheap paxos will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4184407