US5884018A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for distributed agreement on processor membership in a multi-processor system
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1997-01-28
•
Granted: 1999-03-16
•
Expires: 2017-01-28
Abstract
Abstract An apparatus and protocol to determine the group of processors that will survive communications faults and/or timed-event failures in a multiprocessor system. The processors each have a respective memory, and the processors are coupled by means of an inter-processor communication network. The processors detect that the set of processors with which they can communicate has changed. They can choose to either halt or continue operations based on minimizing the likelihood that disconnected groups of processors will continue to operate as independent systems. The processors construct a connectivity matrix on the initiation of a regroup operation. The connectivity information is used to ensure that all the processors in the final group that survives can communicate with all other processors in the group. One or more processors may halt to achieve this characteristic. A processor is suspected of having ceased operations or having a failed timer mechanism when other processors detect the absence of a periodic message from the processor. When this happens, all of the processors are subjected to a series of stages in which they repeatedly broadcast their status and connectivity to each other. The suspected processor does not advance through the stages if it has ceased operations or if its timer mechanism has failed.
Inventors
- 👤 Robert L. Jardine
- 👤 Murali Basavaiah
- 👤 Karoor S. Krishnakumar
- 👤 Srinivasa D. Murthy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 23:11
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/0703; G06F11/0706; G06F11/0721; G06F11/0724; G06F11/14; G06F11/1402; G06F11/1415; G06F11/142; G06F11/1425; G06F11/0751; G06F11/0754; G06F11/0757
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
167 words
In a multi-processor system having a plurality of processors, each of said plurality of processors having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively coupling said plurality of processors; then detecting a communications failure; then attempting to firstly determine on each of said plurality of processors still operating which of said plurality of processors are still operating and still communicatively coupled, thereby determining said each processor's respective view of said multi-processor system; then secondly determining on said each processor still operating whether said each processor still operating is to continue operations or to halt operations, said second determination based on said each processor's respective view of said multi-processor system; then continuing or halting operations on said each processor according to said second determination; collecting connectivity information on a first of said plurality of processors; and then selecting on said first processor certain of said plurality of processors to cease operations, based on said connectivity information collected.
Claim 2
Dependent Claim
167 words
In a multi-processor system having a plurality of processors, each of said plurality of processors having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively coupling said plurality of processors; then detecting a communications failure; then attempting to firstly determine on each of said plurality of processors still operating which of said plurality of processors are still operating and still communicatively coupled, thereby determining said each processor's respective view of said multi-processor system; then secondly determining on said each processor still operating whether said each processor still operating is to continue operations or to halt operations, said second determination based on said each processor's respective view of said multi-processor system; then continuing or halting operations on said each processor according to said second determination; collecting connectivity information on a first of said plurality of processors; and then selecting on said first processor certain of said plurality of processors to cease operations, based on said connectivity information collected.
Claim 3
Dependent Claim
258 words
In a multi-processor system having a plurality of processors, each of said plurality of processors having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively coupling said plurality of processors; then detecting a communications failure; then attempting to firstly determine on each of said plurality of processors still operating which of said plurality of processors are still operating and still communicatively coupled, thereby determining said each processor's respective view of said multi-processor system, including subjecting said each processor to a method including respective advancement from a first to a second stage, initially placing said each processor in said first stage; then sending status of advancement of one of said plurality of processors; receiving on a second of said plurality of processors said status of advancement of said one processor; after said receiving, updating status of said second processor only if notification of a time expiration has occurred on said second processor; respectively advancing to said second stage each processor which has updated its status; determining that timer expirations have failed on said second processor when said second processor fails to advance from said first stage and thus that said second processor has effectively ceased to operate; and then secondly determining on said each processor still operating whether said each processor still operating is to continue operations or to halt operations, said second determination based on said each processor's respective view of said multi-processor system; then continuing or halting operations on said each processor according to said second determination.
Claim 4
Dependent Claim
258 words
In a multi-processor system having a plurality of processors, each of said plurality of processors having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively coupling said plurality of processors; then detecting a communications failure; then attempting to firstly determine on each of said plurality of processors still operating which of said plurality of processors are still operating and still communicatively coupled, thereby determining said each processor's respective view of said multi-processor system, including subjecting said each processor to a method including respective advancement from a first to a second stage, initially placing said each processor in said first stage; then sending status of advancement of one of said plurality of processors; receiving on a second of said plurality of processors said status of advancement of said one processor; after said receiving, updating status of said second processor only if notification of a time expiration has occurred on said second processor; respectively advancing to said second stage each processor which has updated its status; determining that timer expirations have failed on said second processor when said second processor fails to advance from said first stage and thus that said second processor has effectively ceased to operate; and then secondly determining on said each processor still operating whether said each processor still operating is to continue operations or to halt operations, said second determination based on said each processor's respective view of said multi-processor system; then continuing or halting operations on said each processor according to said second determination.
Claim 5
Dependent Claim
188 words
In a multi-processor system having a plurality of processors each having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively connecting said plurality of processors; subjecting each of said plurality of processors to a method including respective advancement from a first to a second stage, initially placing said each processor in said first stage; sending status of advancement of a first of said plurality of processors; receiving on a second of said plurality of processors said status of advancement of said first processor; after said receiving, updating status of said second processor only if notification of a time expiration has occurred on said second processor; respectively advancing to said second stage each processor which has updated its status; and failing to send connectivity information when said second processor fails to advance from said first stage and determining that said second processor has effectively ceased to operate; collecting connectivity information on a third of said plurality of processors; and selecting on said third processor certain of said plurality of processors to cease operations, based on said connectivity information collected.
Claim 6
Dependent Claim
188 words
In a multi-processor system having a plurality of processors each having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively connecting said plurality of processors; subjecting each of said plurality of processors to a method including respective advancement from a first to a second stage, initially placing said each processor in said first stage; sending status of advancement of a first of said plurality of processors; receiving on a second of said plurality of processors said status of advancement of said first processor; after said receiving, updating status of said second processor only if notification of a time expiration has occurred on said second processor; respectively advancing to said second stage each processor which has updated its status; and failing to send connectivity information when said second processor fails to advance from said first stage and determining that said second processor has effectively ceased to operate; collecting connectivity information on a third of said plurality of processors; and selecting on said third processor certain of said plurality of processors to cease operations, based on said connectivity information collected.
Claim 7
Dependent Claim
291 words
In a multi-processor system having a plurality of processors, each of said plurality of processors having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively coupling said plurality of processors; then detecting a communications failure; then attempting to firstly determine on each of said plurality of processors still operating which of said plurality of processors are still operating and still communicatively coupled, thereby determining said each processor's respective view of said multi-processor system, including subjecting said each processor to a method including respective advancement from a first to a second stage, initially placing said each processor in said first stage; then sending status of advancement of one of said plurality of processors; receiving on a second of said plurality of processors said status of advancement of said one processor; after said receiving, updating status of said second processor only if notification of a time expiration has occurred on said second processor; respectively advancing to said second stage each processor which has updated its status; determining that timer expirations have failed on said second processor when said second processor fails to advance from said first stage and thus that said second processor has effectively ceased to operate; and then secondly determining on said each processor still operating whether said each processor still operating is to continue operations or to halt operations, said second determination based on said each processor's respective view of said multi-processor system; then continuing or halting operations on said each processor according to said second determination; collecting connectivity information on a third of said plurality of processors; and then selecting on said third processor certain of said plurality of processors to cease operations, based on said connectivity information collected.
Claim 8
Dependent Claim
291 words
In a multi-processor system having a plurality of processors, each of said plurality of processors having a respective memory, a method for distributively agreeing on processor membership in said multi-processor system, said method comprising: communicatively coupling said plurality of processors; then detecting a communications failure; then attempting to firstly determine on each of said plurality of processors still operating which of said plurality of processors are still operating and still communicatively coupled, thereby determining said each processor's respective view of said multi-processor system, including subjecting said each processor to a method including respective advancement from a first to a second stage, initially placing said each processor in said first stage; then sending status of advancement of one of said plurality of processors; receiving on a second of said plurality of processors said status of advancement of said one processor; after said receiving, updating status of said second processor only if notification of a time expiration has occurred on said second processor; respectively advancing to said second stage each processor which has updated its status; determining that timer expirations have failed on said second processor when said second processor fails to advance from said first stage and thus that said second processor has effectively ceased to operate; and then secondly determining on said each processor still operating whether said each processor still operating is to continue operations or to halt operations, said second determination based on said each processor's respective view of said multi-processor system; then continuing or halting operations on said each processor according to said second determination; collecting connectivity information on a third of said plurality of processors; and then selecting on said third processor certain of said plurality of processors to cease operations, based on said connectivity information collected.
References Cited (Backward Citations)
US4817091A
Cited
US4321666A
Cited
US4323966A
Cited
US4356546A
Cited
US4718002A
Cited
US4757442A
Cited
US5301309A
Cited
US5692119A
Cited
US5452441A
Cited
US5592610A
Cited
US5687308A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |