Electrical computers and digital processing systems: multicomput – Distributed data processing
Reexamination Certificate
2011-08-23
2011-08-23
Pwu, Jeffrey (Department: 2478)
Electrical computers and digital processing systems: multicomput
Distributed data processing
Reexamination Certificate
active
08005888
ABSTRACT:
A conflict tolerant message delay reducing consensus algorithm is presented for operating a distributed computing system. The devices of the distributed computing system can directly receive client requests, and can execute the requests and respond directly to the clients, saving message delays. If there is a conflict, the ultimately selected request can be the request submitted by the client with the highest client identifier. A device can change its vote, and execute a different request, if it is made by a client having a more dominant client identifier. All but one of the clients can also be a device implementing the system. A device that has executed a requested function may no longer submit a request in the same step. Consequently, a request is executed by the system when all devices have executed the request. If one or more devices fails, any fault tolerant consensus algorithm can be used.
REFERENCES:
patent: 5261085 (1993-11-01), Lamport
patent: 6449641 (2002-09-01), Moiin et al.
patent: 6463532 (2002-10-01), Reuter et al.
patent: 6532494 (2003-03-01), Frank et al.
patent: 6671821 (2003-12-01), Castro et al.
patent: 7191357 (2007-03-01), Holland et al.
patent: 2002/0112198 (2002-08-01), Lim et al.
patent: 2003/0023680 (2003-01-01), Shirriff
patent: 2003/0227392 (2003-12-01), Ebert et al.
patent: 2004/0254984 (2004-12-01), Dinker
patent: 2005/0132154 (2005-06-01), Rao et al.
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. 6th, 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 Echo Replicated File System; Digital Equipment Corp. Systems Research Center, Research Report 104, pp. 1-39, Jun. 1993.
Long, Darrell D.E. et al.;Voting with Regenerable Volatile Witnesses; University of California Computer and Information Sciences; Technical Report, pp. 1-20, Apr. 1990.
Swart, Garret et al.;Availability in the Echo File System; Digital Equipment Corp. Systems Research Center, Research Report 112, pp. 1-43, Sep. 1993.
Adya, A., et al.; FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment.;In Proc. 5thOSDI, Boston, MA, pp. 1-14, Dec. 2002.
Castro, M.,Practical Byzantine Fault Tolerance; Ph.D. Thesis Technical Report MIT-LCS-TR-817, MIT, Jan. 2001.
Chockler, G. V., et al., Group Communication Specifications: A Comprehensive Study,ACM Computing Surveys, pp. 33(4):427-469, Dec. 2001.
Deprisco, R., et al., Revisiting the Paxos Algorithm;In Proc. 11thInt'l. Workshop on Distributed Algorithms, pp. 111-125, Sep. 1997.
Lamport, L., Using Time Instead of Timeout for Fault Tolerance in Distributed Systems;ACM Transaction on Programming Languages and Systems(TOPLAS), pp. 6(202):264-280, Apr. 1984.
Lamport, L., et al., Cheap Paxos;In Proc. International Conference on Dependable Systems and Networks(DSN), Florence, Italy, 2004.
Lynch, N., et al., RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks;In Proc. 16thInternational Symposium on Distributed Computing, Toulouse, France, pp. 173-190, Oct. 2002.
Narasimhan, P., et al.,Replica Consistency of CORBA Objects in Partitionable Distributed Systems, 1997.
Oki, B.M.,Viewstamped Replication for Highly Available Distributed Systems; Ph.D. Thesis Technical Report MIT/LCS/TR-423, MIT, Aug. 1988.
Oki, B.M., et al., Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems;In Proc. 7thSymposium on Principles of Distributed Computing, Aug. 1988, pp. 8-17.
Rodrigues, R., et al., BASE: Using Abstractions to Improve Fault Tolerance;In Proc. 18thACM Symposium on Operating System Principles, Bantt, Canada, pp. 15-28, Oct. 2001.
Schneider, F.B., Synchronization in Distributed Programs; ACM Transactions on Programming Languages and Systems (TOPLAS; pp. 4(2):125-148.), Apr. 1982.
Yu, H., et al., Consistent and Automatic Replica Regeneration;In Proc. 1stNSDI, San Francisco, CA, pp. 323-236, 2004.
Pedone, F., et al., Handling Message Semantics with Generic Broadcast Protocols,Distributed Computing15, pp. 97-107, 2002.
Cukier, M., et al., AQuA: An Adaptive Architecture that Provides Dependable Distributed Objects,In Proc. 17thSymposium on Reliable Distributed Systems, pp. 245-253, West Lafayette, IN, Oct. 1998.
Cukier, M., et al., AQuA: An Adaptive Architecture that Provides Dependable Distributed Objects,IEEE Transactions on Computers, vol. 52, No. 1, pp. 31-50, Jan. 2003.
Charron-Bost, Bernadette, et al., Uniform Consensus is Harder than Consensus (extended abstract),Technical Report DSC/2000/028, Switzerland, May 2000.
DePrisco, Robert, et al., Revisiting the PAXOS Algorithm,Theroretical Computer Science, 243:35-91, 2000.
Fischer, Michael J., et al., Impossibility of Distributed Consensus with One Faulty Process,Journal of the ACM, 32(2):374-382, Apr. 1985.
Lamport, Leslie, Lower Bounds for Asynchronous Consensus, inFuture Distributed Computing, vol. 2584 of Lecture Notes in Computer Science, pp. 22-23, Spring, 2003.
Mazurkiewicz, A.,Semantics of Concurrent Sytems; A Modular Fixed-Point Trace Approach; Institute of Computer Science, Poland, pp. 353-375, (1984).
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://theory.1cs.mit.edu/˜roger/Research/Papers/khazan-phd.pdf.
Anceaume et al., “Converging Toward Decision Conditions”6thInternational Conference on Principles of Distributed Syst
Microsoft Corporation
Pwu Jeffrey
Sciacca Scott M
Woodcock & Washburn LLP
LandOfFree
Conflict fast consensus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Conflict fast consensus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conflict fast consensus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2719603