Method of seeking consensus among computer processes

Details Method of seeking consensus among computer processes Method of seeking consensus among computer processes

2008-05-20

2008-05-20

McCarthy, Christopher S (Department: 2113)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C718S101000, C718S001000

Reexamination Certificate

active

07376867

ABSTRACT:
An embodiment of a method of seeking consensus among computer processes begins with a first step of saving a new timestamp in a timestamp array for a particular process. The method continues with a second step of determining whether a most recent entry in a decision array includes a previously established consensus decision. In a third step, if the most recent entry does not include the previously established consensus decision, the method saves a proposed decision as a consensus decision. Otherwise, in a fourth step, the method saves the previously established consensus decision as the consensus decision. In a fifth step, if a most recent timestamp in the timestamp array continues to be the new timestamp, the method returns the consensus decision. Otherwise, in a sixth step, the method returns an abort indicator.

REFERENCES:
patent: 5471631 (1995-11-01), Beardsley et al.
patent: 5907701 (1999-05-01), Hanson
patent: 6078930 (2000-06-01), Lee et al.
patent: 6295541 (2001-09-01), Bodnar et al.
patent: 6651242 (2003-11-01), Hebbagodi et al.
patent: 6687847 (2004-02-01), Aguilera et al.
patent: 6754845 (2004-06-01), Kursawe et al.
patent: 6854115 (2005-02-01), Traversat et al.
patent: 6898733 (2005-05-01), Parks et al.
patent: 2001/0056420 (2001-12-01), Steele et al.
patent: 2004/0015510 (2004-01-01), Moir et al.
Aguilera et al., Strict Linearizability and the Power of Aborting, HPL-2003-241, Dec. 8, 2003, Hewlett-Packard, Palo Alto, CA.
Michael Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, 1983, ACM Press, New York, NY.
Chandra et al., Unreliable failure detectors for reliable distributed systems, Journal of the ACM, 1996, 43(2):225-267, ACM Press, New York, NY.
Flaviu Cristian, Understanding Fault-Tolerant Distributed Systems, 1993. <ftp://ftp.cs.ucsd.edu/pub/team/understandingftsystems.ps.Z>.
Dolev et al., On the Minimal Synchronism Needed for Distributed Consensus, Journal of the ACM, 1987, 34(1):77-97, ACM Press, New York, NY.
Dutta et al., An Efficient Universal Construction for Message-Passing Systems, (Preliminary Version), Technical Report EFPL/IC/2002/28, 2002, Swiss Federal Institute of Technology, Lausanne, Switzerland.
Dwork et al., Consensus in the Presence of Partial Synchrony, Journal of the ACM, 1988, 35(2):288-323, ACM Press, New York, NY.
Fischer et al., Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM, 1985, 32(2):374-382, ACM Press, New York, NY.
Felix C. Gärtner, Fundamentals of Fault-Tolerant Distributed Computing Asynchronous Environments, ACM Computing Surveys, 1999, 31(1):1-26, ACM Press, New York, NY.
Maurice Herlihy, Wait-Free Synchronization, ACM Transactions on Programming Languages and Systems, 1991, 11(1):124-149, ACM Press, New York, NY.
Hurfin et al., A simple and fast asynchronous consensus protocol based on a weak failure detector, Distributed Computing, 1999, 12(4):209-223, Springer-Verlag, Berlin, Germany.
Lamport et al., The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems, 1982, 4(3):382-401, ACM Press, New York, NY.
Lamport et al., Specifying and Verifying Fault-Tolerant Systems, 1994. <http://www.research.digital.com/SRC/personal/lamport/tla/ftrtft94.ps.Z>.
Leslie Lamport, The Part-Time Parliament, ACM Transactions on Computer Systems, 1998, 16(2):133-169, ACM Press, New York, NY.
Butler W. Lampson, How to Build a Highly Available System Using Consensus, 1996. <http://www.ece.cmu.edu/˜ganger/712.fall00/papers/Lampson.pdf.gz>.
Loui et al., Memory Requirements For Agreement Among Unreliable Asynchronous Processes, Advances in Computing Research, 1987, 4:163-183, JAI Press, Greenwich, CT.
André Schiper, Early consensus in an asynchronous system with a weak failure detector, Distributed computing, 1997, Springer-Verlag, Berlin, Germany.
Fred B. Schneider, Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial, ACM Computing Surveys, 1990, 22(4):299-319, ACM Press, New York, NY.

Affiliated with

Also associated with

Rating

Method of seeking consensus among computer processes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of seeking consensus among computer processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of seeking consensus among computer processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2787543