Cheap paxos

Details Cheap paxos Cheap paxos

2007-07-24

2007-07-24

Beausoliel, Robert (Department: 2113)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C714S004110, C714S006130, C714S010000, C714S012000

Reexamination Certificate

active

10872338

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: 6108699 (2000-08-01), Moiin
patent: 6192401 (2001-02-01), Modiri et al.
patent: 6671821 (2003-12-01), Castro et al.
patent: 2003/0023680 (2003-01-01), Shirriff
Neilsen-M-L, A dynamic probe strategy for quorum systems, IEEE, Abstract.
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;Prcc. 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 Hybrd 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-Thoughput 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 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 on Archival Intermemory;International Forum on Reserach 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; May 1996; pp. 1-11.
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; Aug. 2002; pp. 1-11.
Awerbuch, Baruch et al.;Maintaining Database Consistency in Peer to Peer Networks; Department of Computer Science, John Hopkins University; Technical Report CNDS-2002-1; Feb. 6, 2002; pp. 1-14.
Birrell, Andrew D. et al.;The Echo Distributed File System; Digital Equipment Corp. Systems Research Center; Technical Report 111; Sep. 10, 1993; pp. 1-22.
Liskov, Barbara et al.;Replication in the Harp File System; Proceedings of the 13thSymposium on Operating System Principles; Oct. 1991; 13 pp.
Hisgen, Andy et al.;New-Value Logging in the Echo Replicated File System; Digital Equipment Corp. Systems Research Center, Research Report 104; Jun. 1993; pp. 1-39.
Long, Darrell D.E. et al.;Voting with Regenerable Volatile Witnesses; University of California Computer and Information Sciences; Technical Report; Apr. 1990; pp. 1-20.
Swart, Garret et al.;Availability in the Echo File System; Digital Equipment Corp. Systems Research Center, Research Report 112; Sep. 1993; pp. 1-43.
Adya, A., et al.; FARSITE: Federated, Available, and Re

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3774333