US5727210A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fault tolerant load management system and method
Assignee: International Business Machines Corp
•
Filing: 1995-07-26
•
Granted: 1998-03-10
•
Expires: 2015-07-26
Abstract
Abstract A method and apparatus are disclosed for managing tasks in a network of processors. After a period of time has elapsed, during which the processors of the network have been executing tasks allocated to them, the processors exchange views as to which pending tasks have or have not been completed. The processors reach a consensus as to the overall state of completion of the pending tasks. In a preferred embodiment, the processors exchange views and update their views based on the views received from the other processors. A predetermined condition determines that a consensus has been reached. The predetermined condition is preferably two sets of exchanges in which a processor has received messages from the same set of other processors. Alternatively, the condition is an exchange which does not result in any updates to a processor's view. A processor which has not sent a view as part of an exchange is deemed to have crashed, and the tasks previously allocated to crashed processors are assumed not to have been completed. All pending tasks including those previously allocated but not completed, are then allocated. Preferably, allocation is based on an estimation that approximately the same time will be required for each processor to complete its allocated tasks. Based on this estimation, a time is scheduled for the next exchange of views, and the processors then resume executing their allocated tasks.
Inventors
- 👤 Cynthia Dwork
- 👤 Joseph Y. Halpern
- 👤 Hovey R. Strong, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 05:08
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/20; G06F11/202; G06F11/2023; G06F11/14; G06F11/1402; G06F11/1415; G06F11/142; G06F11/1425; G06F11/2035
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
167 words
A computer program product, for use with a processor in a multiprocessing network including a plurality of processors, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the processor to determine, along with other operational processors of the multiprocessing network, which tasks, previously allocated to various ones of the processors, have not been executed, the means for directing to determine including: means, recorded on the recording medium, for directing the processor to exchange views between itself and the other operational processors to reach consensus among the operational processors as to the status of the previously allocated tasks, each view including at least one of: (a) information on what work has been done by the processor sending the view; and (b) information on what work, done by other processors, has been reported to the processor sending the view; and means, recorded on the recording medium, for directing the processor to allocate pending tasks between the processor and the other operational processors.
Claim 2
Dependent Claim
167 words
A computer program product, for use with a processor in a multiprocessing network including a plurality of processors, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the processor to determine, along with other operational processors of the multiprocessing network, which tasks, previously allocated to various ones of the processors, have not been executed, the means for directing to determine including: means, recorded on the recording medium, for directing the processor to exchange views between itself and the other operational processors to reach consensus among the operational processors as to the status of the previously allocated tasks, each view including at least one of: (a) information on what work has been done by the processor sending the view; and (b) information on what work, done by other processors, has been reported to the processor sending the view; and means, recorded on the recording medium, for directing the processor to allocate pending tasks between the processor and the other operational processors.
Claim 3
Dependent Claim
75 words
A computer program product as recited in claim 1, wherein the means for directing to allocate includes: means, recorded on the recording medium, for directing the processor to estimate the length of time required to complete each of the pending tasks; and means, recorded on the recording medium, for directing the processor to allocate the tasks such that each of the processors will require approximately the same total time for completion of its allocated tasks.
Claim 4
Dependent Claim
39 words
A computer program product as recited in claim 1, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to initially transmit a message stating what work the processor has executed.
Claim 5
Dependent Claim
57 words
A computer program product as recited in claim 3, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to receive messages initially transmitted by the other operational processors of the network, and to incorporate the received messages into the processor's view as to what tasks have been executed.
Claim 6
Dependent Claim
38 words
A computer program product as recited in claim 1, further comprising means, recorded on the recording medium, for directing the processor to schedule a future time at which the means for exchanging and allocating are to operate again.
Claim 7
Dependent Claim
117 words
A computer program product as recited in claim 5, wherein: the means for directing to allocate includes: means, recorded on the recording medium, for directing the processor to estimate the length of time required to complete each of the pending tasks, and means, recorded on the recording medium, for directing the processor to allocate the tasks such that each of the processors will require approximately the same total time for completion of its allocated tasks; and the means for directing to schedule includes means, recorded on the recording medium, for directing the processor to select the future time based on the approximately the same total time for completion of the allocated tasks by each of the processors.
Claim 8
Dependent Claim
67 words
A computer program product as recited in claim 1, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to make exchanges, each exchange including transmitting the processor's view, to receive transmitted views from the other processors, and to update the processor's view based on the received views, until a predetermined condition indicative of a consensus has been reached.
Claim 9
Dependent Claim
39 words
A computer program product as recited in claim 7, wherein, in the means for directing to exchange, the predetermined condition is that, for two exchanges of views, the processor receives messages from the same set of other operational processors.
Claim 10
Dependent Claim
38 words
A computer program product as recited in claim 7, wherein, in the means for directing to exchange, the predetermined condition is that, for two exchanges of views, the processor's view does not change based on any views received.
Claim 11
Dependent Claim
69 words
A computer program product as recited in claim 7, further comprising: means, recorded on the recording medium, for directing the processor, responsive to the predetermined condition being achieved, to transmit a message that the condition has been reached; and means, recorded on the recording medium, for directing the processor to terminate the step of exchanging responsive to transmission or receipt of a message that the condition has been reached.
Claim 12
Dependent Claim
47 words
A computer program product as recited in claim 1, wherein the means for directing to determine includes means, recorded on the recording medium, for directing the processor to determine, along with the other operational processors of the multiprocessing system, which of the plurality of processors have failed.
Claim 13
Dependent Claim
37 words
A computer program product as recited in claim 11, wherein the step of determining the failed processors includes determining that a processor which did not transmit a view as part of an exchange of views has failed.
Claim 14
Dependent Claim
46 words
A computer program product as recited in claim 12, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to determine that tasks previously allocated to the processor which is determined to have failed have not been executed.
Claim 15
Dependent Claim
71 words
A computer program product as recited in claim 13, wherein the means for directing to allocate includes means, recorded on the recording medium, for directing the processor to allocate previously pending tasks which were allocated in a previous operation of the means for reaching and allocating, but which have not been executed, and to allocate tasks which became pending subsequent to the previous operation of the means for reaching and allocating.
Claim 16
Dependent Claim
168 words
A computer program product, for use with a processor in a multiprocessing network including a plurality of processors, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the processor to determine, along with other operational processors of the multiprocessing network, which ones of the plurality of processors have failed, the means for directing to determine including: means, recorded on the recording medium, for directing the processor to exchange views between itself and the other operational processors to reach consensus among the operational processors as to the operational status of the plurality of processors known to the operational processors, each view including at least one of: (a) information on what work has been done by the processor sending the view, and (b) information on what work, done by other processors, has been reported to the processor sending the view; and means, recorded on the recording medium, for directing the processor to allocate pending tasks between the processor and the other operational processors.
Claim 17
Dependent Claim
168 words
A computer program product, for use with a processor in a multiprocessing network including a plurality of processors, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the processor to determine, along with other operational processors of the multiprocessing network, which ones of the plurality of processors have failed, the means for directing to determine including: means, recorded on the recording medium, for directing the processor to exchange views between itself and the other operational processors to reach consensus among the operational processors as to the operational status of the plurality of processors known to the operational processors, each view including at least one of: (a) information on what work has been done by the processor sending the view, and (b) information on what work, done by other processors, has been reported to the processor sending the view; and means, recorded on the recording medium, for directing the processor to allocate pending tasks between the processor and the other operational processors.
Claim 18
Dependent Claim
37 words
A computer program product as recited in claim 15, wherein the step of determining the failed processors includes determining that a processor which did not transmit a view as part of an exchange of views has failed.
Claim 19
Dependent Claim
37 words
A computer program product as recited in claim 15, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to initially transmit a message reflecting the processor's operational status.
Claim 20
Dependent Claim
60 words
A computer program product as recited in claim 17, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to receive messages initially transmitted by the other operational processors of the network, and to incorporate the received messages into the processor's view as to the operational status of the plurality of processors.
Claim 21
Dependent Claim
67 words
A computer program product as recited in claim 15, wherein the means for directing to exchange includes means, recorded on the recording medium, for directing the processor to make exchanges, each exchange including transmitting the processor's view, to receive transmitted views from the other processors, and to update the processor's view based on the received views, until a predetermined condition indicative of a consensus has been reached.
Claim 22
Dependent Claim
39 words
A computer program product as recited in claim 19, wherein, in the means for directing to exchange, the predetermined condition is that, for two exchanges of views, the processor receives messages from the same set of other operational processors.
Claim 23
Dependent Claim
38 words
A computer program product as recited in claim 19, wherein, in the means for directing to exchange, the predetermined condition is that, for two exchanges of views, the processor's view does not change based on any views received.
Claim 24
Dependent Claim
69 words
A computer program product as recited in claim 19, further comprising: means, recorded on the recording medium, for directing the processor, responsive to the predetermined condition being achieved, to transmit a message that the condition has been reached; and means, recorded on the recording medium, for directing the processor to terminate the step of exchanging responsive to transmission or receipt of a message that the condition has been reached.
References Cited (Backward Citations)
US4126895A
Cited
US4817091A
Cited
US4318173A
Cited
US4323966A
Cited
US4333144A
Cited
US4356546A
Cited
US4710926A
Cited
US4852001A
Cited
US4805107A
Cited
US4958273A
Cited
US5012409A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-09 | 2001-09-08 | 2002-03-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-09 | 2005-09-08 | 2006-03-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-09 | 2009-09-08 | 2010-03-10 | $7700.00 | Window Closed / Lapsed |