Patent ID: 7792015

Claim:
A system capable of self-stabilizing from an arbitrary state in the presence of a bounded number of Byzantine faults, the system comprising: a plurality of nodes in communication with each other node, each node comprising: a state machine: a plurality of monitors, a quantity of monitors being equal to one less than a quantity of nodes, each monitor in communication with the state machine, each monitor configured to receive self-stabilization messages from a different corresponding node and configured to determine a current state of the corresponding node; a local physical oscillator; and two logical time clocks driven by the local physical oscillator; wherein the state machine is configured to describe a current state of the node, the current state comprising either a maintain-state or a restore-state; wherein the state machine is configured to transmit self-stabilization messages to all other nodes, the self-stabilization messages comprising either a Resync message indicating that the node is attempting to engage in resynchronization with all other nodes or an Affirm message indicating that the node is transitioning to another state in an attempt to synchronize or indicating that the node is currently synchronized; wherein the state machine transitions the node from the maintain-state to the restore-state if a predefined number of valid Resync messages have been received; wherein the state machine transitions the node from the restore-state to the maintain-state if (1) the node is in the restore-state, (2) a predefined number of events have occurred within a same number of predefined time intervals, each event occurring when a predefined number of valid self-stabilization messages have been received by the monitors within one predefined time interval, and (3) the monitors have not received a valid Resync message during a most recent event occurrence; wherein the system does not comprise a central dock used by the nodes for self-stabilization; and wherein the nodes do not use an externally generated global pulse for self-stabilization.