Patent ID: 8861552

Claim:
A self-stabilizing network comprising: a node that includes: a synchronizer; a set of monitors in communication with the synchronizer, wherein each monitor in the set of monitors is configured to receive a transmitted Sync message, and wherein the number of monitors in the set of monitors is no more than one fewer than the number of nodes in the network; a physical oscillator; and a logical time clock driven by the physical oscillator and having a variable clock value that locally tracks the passage of clock time for the node; wherein the synchronizer, without using a global clock or a globally-generated signal, globally-generated pulse, or globally-generated message of any kind for self-stabilization, executes a predetermined protocol to thereby: set the clock value equal to 0 when the clock value is less than 0; set the clock value equal to between 0 and a communication latency value (γ) when the Sync message is received by the synchronizer and the clock value is less than a minimum event-response delay (D); set the clock value equal to between 0 and γ and transmit a new Sync message when: the Sync message is received by the synchronizer; and the clock value is greater than or equal to both D and to a calibrated graph threshold (T S ); set the clock value to 0 and transmit a new Sync message when the Sync message is not received by the synchronizer and the clock value is greater than or equal to a calibrated resynchronization period (P); and increment the clock value when the Sync message is not received by the synchronizer and the clock value is less than P; wherein the network is an arbitrary, non-partitioned digraph that is self-stabilizing, via execution of the protocol, from any initial state, and wherein the synchronizer transmits the Sync message to as many other nodes in the network as are directly connected to the first node.