Method and system for achieving collective consistency in detect

Details Method and system for achieving collective consistency in detect Method and system for achieving collective consistency in detect

1995-09-01

1997-10-28

Beausoliel, Jr., Robert W.

39518211, 39518202, 3951851, 39520011, G06F 1100

Patent

active

056824700

ABSTRACT:
A method and apparatus are disclosed for achieving collective consistency in the detection and reporting of failures in a distributed computing system having multiple processors. Each processor is capable of being called by a parallel application for system status. Initially, each processor sends the other processors its view on the status of the processors. It then waits for similar views from other processors except those regarded as failed in its own view. If the received views are identical to the view of the processor, the processor returns its view to the parallel application. In a preferred embodiment, if the views are not identical to its view, the processor sets its view to the union of the received views and its current view. The steps are then repeated. Alternately, the steps are repeated if the processor does not have information that each of the processors not regarded as failed in its view forms an identical union view. In another preferred embodiment, the method is terminated if a quorum is not formed by the processors which are not regarded as failed. Alternatively, after sending its view, the processor waits for an exit condition. Depending on the exit condition, the processor sets its view to a quorum view and sends a "DECIDE" message to the other processors. In another embodiment, the processor updates its view and the method steps are repeated.

REFERENCES:
patent: 4055808 (1977-10-01), Holsinger et al.
patent: 4323966 (1982-04-01), Whiteside et al.
patent: 4545011 (1985-10-01), Lyon et al.
patent: 4569015 (1986-02-01), Dolev et al.
patent: 4710926 (1987-12-01), Brown et al.
patent: 4914657 (1990-04-01), Walter et al.
patent: 5206952 (1993-04-01), Sundet et al.
patent: 5365512 (1994-11-01), Combs et al.
patent: 5377322 (1994-12-01), Ogura et al.
patent: 5408649 (1995-04-01), Beshears et al.
patent: 5436909 (1995-07-01), Dev et al.
patent: 5485465 (1996-01-01), Liu et al.
patent: 5506955 (1996-04-01), Chen et al.
patent: 5513354 (1996-04-01), Dwork et al.
patent: 5519830 (1996-05-01), Opoczynski
Vaidya et al., "Degradable Agreement in the Presence of Byzantine Faults", Distributed Computig syustems, 1993 Int'l Conf. IEEE, pp.237-244, 1993.
Becker, "Keeping Processes Under Surveillance", Reliable Distributed systems, 1991, 10th Symposium, IEEE, pp. 198-205.
Ng, "Ordered Broadcasts for Large Applications", Reliable Distributed Systems, 1991, 10th Symposium, IEEE, pp.188-197.
Yan et al., "Otimal Agreement Protocol in Malicious Faulty Processors and Faulty Links", IEEE Trans. on Knowledge and Data Eng., 1992, pp. 266-280.
Barborak et al., "Partitioning for Efficient Consensus" System Sciences, 1993 Annual Int'l Conf., IEEE, pp. 438-446, 1993.
Soufi et al. "An O(1) Quorem C Onsensus Protocol Tailored for TEH Client/Server Architecture", Reliable Distributed systems, 1993 12th Symposium, IEEE, pp. 98-104, 1993.
D. Malki et al., Uniform Action in Asynchronous Distributed Systems, (Extended Abstract), ACM 0-89791-654-9/94/0008, pp. 274-283.
M. Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols (Extended Abstract), ACM 0-89791-110-5/83/008/0027, pp. 27-30.
T. D. Chandra et al., The Weakest Failure Detector for Solving Consensus, ACM 0-89791-496-1/92/0008/0147, pp. 147-158.
J. Dongarra et al., MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, Tennessee, 1993-1994, pp. 1-11 & pp. 90-129.

Affiliated with

Also associated with

Rating

Method and system for achieving collective consistency in detect 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 and system for achieving collective consistency in detect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for achieving collective consistency in detect will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1031472