DECENTRALIZED SYNCHRONIZATION OF CLOCKS

A method for synchronizing clocks in a distributed computing system in the presence of faults. The condition to be renewed guarantees that all clocks of correct processors never deviate by more than some maximum amount. This condition is achieved by periodically resynchronizing the clocks so that the correct clocks do not deviate by more than some minimum deviation. In the process of resynchronization, a correct clock is never adjusted by more than a maximum amount during a period and it is never set back. The method requires ascertaining whether a valid time value message has been received within a specified period. A message is valid if it was received within an interval predetermined as a function of the number of signatures from other processors appending the message. If the valid message has not been received within the current period, then the local processor originates and broadcasts to all processors exactly one time value message and appends thereto its unforgeable signature. On the other hand if a valid message has been received, then the local processor appends its unforgeable signature to the message and passes exactly the one message on by broadcasting to all processors. As part of the protocol involving broadcasting of a message, each processor resets the time for expected resynchronization and updates its local clock.