Method for multiprocessor communications

Claim 3

The method for communicating updated information set forth in claim 1 wherein the step of broadcasting the update message comprises sending the update message to each processor in accordance with the predetermined order.

Claim 4

The method for communicating updated information set forth in claim 1 wherein the step of developing an update message includes the step of providing an update sequence number for the message.

Claim 5

The method for communicating updated information set forth in claim 1 wherein the step of selecting one of the processors as sender processor includes the step of allocating an update semaphore by the control processor to the selected sender processor throughout the broadcast.

Claim 6

The method for communicating updated information set forth in claim 4 wherein the step of allocating an update semaphore includes the step of setting a lock bit in an initial transmission of the message to the control processor in order to set the update semaphore, and wherein the step of broadcasting the message to the other processors includes the step of sending the lock bit cleared in each message transmitted to the other processors.

Claim 7

The method for communicating updated information set forth in claim 4 comprising an additional step of deallocating the update semaphore at the completion of the broadcast.

Claim 8

The method for communicating updated information set forth in claim 6 wherein the deallocating step is carried out by resending the message to the control processor at the end of the broadcast with the lock bit cleared, as a signal that the broadcast has been completed.

Claim 9

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, broadcasting the message from the sender processor 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.

Claim 10

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, broadcasting the message from the sender processor 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.

Claim 11

The global update method set forth in claim 8 including the further step of 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.

Claim 12

The global update method set forth in claim 8 including the further step of 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.

Claim 13

The global update method set forth in claim 10 comprising a further step in which said next processor rebroadcasts the latest global update message to all other up processors upon becoming locker processor.

Claim 14

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.

Claim 15

The global update method set forth in claim 10 wherein the step of clearing the update lock semaphore area in the next locker processor at the completion of the broadcast comprises the step of resending the message to the next locker processor from itself in order to clear its semaphore area.

Claim 16

The global update method set forth in claim 8 wherein messages are passed on a repetition basis between all processors of the system in order for each processor to monitor current operational status of every other processor.

Claim 17

The global update method set forth in claim 8 wherein the step of broadcasting the message further comprises the step of providing each processor with an update sequence number for the message.

Claim 18

The global update method set forth in claim 8 wherein the step of broadcasting the message from the sender processor to every other processor is carried out as an atomic operation.

Claim 19

The global update method set forth in claim 8 wherein the step of setting the update lock semaphore in the storage area of the locker processor can be carried out only when no other message broadcast is in progress.

Claim 20

The global update method set forth in claim 17 further comprising the step of sending a message to the locker processor which includes setting a lock bit in order to set the update lock semaphore, and wherein the step of broadcasting the message to the other processors includes the step of clearing the lock bit before transmission.

Claim 21

The global update method set forth in claim 15 wherein each processor compares the update sequence number for the message received with the update sequence number previously recorded in the processor corresponding to the last message.

Claim 22

The global update method set forth in claim 19 comprising the step of negatively acknowledging to the sender processor of a message when its update sequence number does not correctly correspond with the previously recorded update sequence number.

Claim 23

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, broadcasting the message from the sender processor 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.

Claim 24

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, broadcasting the message from the sender processor 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.

Claim 25

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, broadcasting the message from the sender processor 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, 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.

Claim 26

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, broadcasting the message from the sender processor 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, 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.

Claim 27

The global update method set forth in claim 22 wherein the step of transferring the locker processor role to the next processor in the order is carried out only after the message has been sent to the next processor in that order.

Claim 28

The 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, broadcasting the message from the sender processor 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, 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.

Claim 29

The 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, broadcasting the message from the sender processor 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, 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.

Claim 30

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, broadcasting the message from the sender processor 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 acknowledging 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.

Claim 31

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, broadcasting the message from the sender processor 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 acknowledging 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.

Claim 32

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 sending an atomic global update message to said locker processor from said sender processor, d. after setting said update lock semaphore in said locker, broadcasting said global update message from said sender processor to every other processor in said order, and 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.

Claim 33

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 sending an atomic global update message to said locker processor from said sender processor, d. after setting said update lock semaphore in said locker, broadcasting said global update message from said sender processor to every other processor in said order, and 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.

Claim 34

The global update method set forth in claim 26 further comprising the step of rebroadcasting of said atomic global update to said remaining processors from said locker processor, in the event that said sender processor fails after it has sent said global update to said locker processor and before it has cleared said update lock semaphore.

Claim 35

The global update method set forth in claim 26 further comprising the step of 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 global update has been sent to said next processor in said order.

Claim 36

The global update method set forth in claim 26 further comprising the step of setting said semaphore to identify said next processor and resending the global update from said next processor as successor locker processor to every other processor, and then resending the global update to said successor locker processor from itself in order to clear said semaphore, in the event that the sender processor and said current locker processor both fail after said atomic global update has been sent to said next processor.

Claim 37

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 sequence number for said message, and a global update message, c. when no other atomic global update is in progress, setting 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, broadcasting said atomic global update message from said sender processor 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 teams 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.

Claim 38

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 sequence number for said message, and a global update message, c. when no other atomic global update is in progress, setting 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, broadcasting said atomic global update message from said sender processor 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 teams 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.

Claim 39

A distributed data processing system comprising a plurality of distributed interconnected processors arranged and adapted for operation in accordance with a method as claimed in any of the preceding claims.