Method for multiprocessor communications
First Claim
1. A method for communicating updated information among processors in a distributed data processing system comprising a plurality of distributed, interconnected processors each having a memory, including the steps of:
- a. prioritizing the processors into a predetermined order;
b. establishing one of the processors as a control processor for the broadcast of update messages;
c. developing an update message having a plurality of bit positions in at least one of the processors;
d. the one processor broadcasting the update message to each of the processors in the following manner;
(1) sending the update message first to the control processor with at least one bit position set to a first state, the control processor acknowledging the update message if no other update message is in the broadcast process;
(2) sending the update message to each of the other processors with the one bit position set to a second state;
(3) sending the update message again to the control processor with the one bit position set to the second state to indicate completion of the broadcast; and
e. causing, in the event the control processor fails, the next processor in order to be selected as the control processor.
4 Assignments
0 Petitions
Accused Products
Abstract
An improved method for communicating updated information among processors in a distributed data processing system. The system includes a plurality of distributed interconnected processors each having a memory. The method includes the steps of prioritizing the processors into a predetermined order, establishing one of the processors as a control processor for the broadcast of update messages, developing an update message in at least one of the processors, selecting in accordance with the control processor one of the processors which has developed an update message as a sender processor, broadcasting the update message of the sender processor to each of the processors, and causing the next processor in order to be selected as control processor in the event that the former control processor fails in service. As one preferred use, the method enables the system to transmit atomic global update messages with a tolerance to multiple processor faults.
109 Citations
26 Claims
-
1. A method for communicating updated information among processors in a distributed data processing system comprising a plurality of distributed, interconnected processors each having a memory, including the steps of:
-
a. prioritizing the processors into a predetermined order; b. establishing one of the processors as a control processor for the broadcast of update messages; c. developing an update message having a plurality of bit positions in at least one of the processors; d. the one processor broadcasting the update message to each of the processors in the following manner; (1) sending the update message first to the control processor with at least one bit position set to a first state, the control processor acknowledging the update message if no other update message is in the broadcast process; (2) sending the update message to each of the other processors with the one bit position set to a second state; (3) sending the update message again to the control processor with the one bit position set to the second state to indicate completion of the broadcast; and e. causing, in the event the control processor fails, the next processor in order to be selected as the control processor. - View Dependent Claims (2, 3)
-
-
4. A multiple fault tolerant global update method in a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:
-
a. identifying an initial locker processor and arranging all of said processors into an order, b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor, c. after setting the update lock semaphore in the locker, the sender processor broadcasting the message to every other processor, d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received, e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast. - View Dependent Claims (5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
8. The global update method set forth in claim 8 for recovering from a failure of the locker processor during a message broadcast, including the further step of setting the semaphore to identify the next processor in the order and resending the message from the next processor as successor locker processor to every other processor.
-
17. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:
-
a. identifying an initial locker processor and arranging all of said processors into an order, b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor, c. after setting the update lock semaphore in the locker, the sender processor broadcasting the message to every other processor, d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received, e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast, and f. rebroadcasting from the locker processor of the message to the remaining processors in the event that the sender processor fails after it has sent the message to the locker processor and before the update lock semaphore area of the locker has been cleared.
-
-
18. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processor including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:
-
a. identifying an initial locker processor and arranging all of said processors into an order, b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending to the locker processor from the sender processor a message having a plurality of bit positions with at least one of the bit position set to a first state, c. after setting the update lock semaphore in the locker, broadcasting the message from the sender processor to every other processor with the bit position set to a second state, d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received, e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast, f. automatically transferring the locker processor role to a next processor in the order in the event that the next processor learns that the current locker processor has failed. - View Dependent Claims (19)
-
-
20. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:
-
a. identifying an initial locker processor and arranging all of said processors into an order, b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor, c. after setting the update lock semaphore in the locker, the sender processor broadcasting the message to every other processor, d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received, e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast, and f. setting the semaphore to identify the next processor in the order and rebroadcasting the message from the next processor as successor locker processor to every other processor, in the event of a failure of the locker processor during a message broadcast.
-
-
21. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:
-
a. identifying an initial locker processor and arranging all of said processors into an order, b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor, c. providing each message with an update sequence number, d. after setting the update lock semaphore in the locker, the sender process broadcasting the message to every other processor. e. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received, f. maintaining a current update sequence number in each processor and negatively acknowleging any message having an update sequence number which does not correspond with the maintained current update sequence number, and g. clearing the update lock semaphore area in the locker processor at the completion of the broadcast.
-
-
22. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving test messages to and from every other of said processors on a repetition basis for thereby enabling each said processor to monitor current operational status of every other of said processors, said method including the steps of:
-
a. ordering said processors into a global update order by which one of said processors is an initial locker processor and every other processor is configured automatically to become locker processor upon failure of the current locker processor in accordance with said order, b. storing in each processor the last global update message including an update lock semaphore for identifying a sender processor, further including an update sequence number for said message, and further including the text of the global update message, c. when no other global update is being broadcast, setting the update lock semaphore in the locker processor to identify a current sender processor by first enabling an atomic global update message to said locker processor from said sender processor, d. after setting said update lock semaphore in said locker, the sender processor broadcasting said global update message to every other processor in said order, and e. clearing said update lock semaphore by resending said atomic global update to said locker professor from said sender processor after it has broadcast said atomic global update to all of said other processors. - View Dependent Claims (23, 24, 25)
-
-
26. A global update method tolerating multiple near simultaneous or simultaneous processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving test messages to and from every other of said processors on a repetition basis for thereby enabling each said processor to monitor current operational status of every other of said processors, said method including the steps of:
-
a. ordering said processors into a global update order by which one of said processors is an initial locker processor and every other processor is configured automatically to become locker processor upon failure of the current locker processor in accordance with said order, b. providing a buffer area in each processor for storing an update lock semaphore for signalling that an atomic global update message is being transferred by a sender processor, an update sequence number for said message, and a global update message, c. when no other atomic global update is in progress, setting said update lock semaphore in the buffer area of said locker processor to identify a sender processor by first sending an atomic global update message to said locker processor from said sender processor, d. after setting said update lock semaphore in said locker, the sender processor broadcasting said atomic global update message to every other processor in said order, e. clearing said update lock semaphore by resending said atomic global update to said locker processor from said sender processor after it has broadcast said atomic global update to all of said other processors, f. if said sender processor fails after it has sent said atomic global update to said locker processor and before it has cleared said update lock semaphore, rebroadcasting of said atomic global update to said remaining processors from said locker processor, g. automatically transferring the locker processor role to the next processor in said order in the event that said next processor learns that said current locker processor has failed after said atomic global update has been sent to said next processor in said order, and h. if said sender processor and said current locker processor both fail after said atomic global update has been sent to said next processor, setting said semaphore to identify said next processor and resending said atomic global update from said next processor as successor locker processor to every other processor, and then resending said atomic global update to said successor locker processor from itself in order to clear said semaphore.
-
Specification