Patent ID: 8255732

Claim:
A method for synchronizing clocks among a plurality of nodes in a system, the plurality of nodes comprising faulty nodes and good nodes having an arbitrary state and in the presence of a bounded number of arbitrary faults, said nodes being capable of communicating with each other by exchanging messages through a set of communication channels, comprising performing the following steps at each node: (1.1) providing a local oscillator clock which provides a local oscillator clock tick; (1.2) executing once every local oscillator clock tick (a) a plurality of operational steps for each of a set of monitors comprising one monitor for and corresponding to each other node in said plurality of nodes, and (b) a plurality of protocol steps for a state machine for each node, wherein the state machine comprises a Restore state and a Maintain state; (1.3) providing a GammaTimer clock and incrementing said GammaTimer clock once per local oscillator clock tick; (1.4) providing a StateTimer clock, and incrementing said StateTimer clock on each equally spaced interval γ comprising one or more local oscillator clock ticks such that γ is equal to or greater than the sum of a minimum event response delay D among said plurality of nodes and a network imprecision d; and (1.5) providing a LocalTimer clock, and incrementing said LocalTimer clock on the local oscillator clock tick.