A new fault-tolerant algorithm for clock synchronization
type: Item
instance of: scholarly article
title: A new fault-tolerant algorithm for clock synchronization
zbMATH Open document ID: 0646.68029
DOI: 10.1016/0890-5401(88)90043-0
author: Jennifer L. Welch
author: Nancy Lynch
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
review text: We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read-only physical clock whose drift rate from real time is very small. By adding a value to its physical clock time, the process obtains its local time. The algorithm solves the problem of maintaining closely synchronized local times, assuming that processes' local times are closely synchronized initially. The algorithm is able to tolerate the failure of just under one-third of the participating processes. It maintains synchronization to within a small constant, whose magnitude depends upon the rate of clock drift, the message delivery time and its uncertainty, and the initial closeness of synchronization. We also give a characterization of how far the clocks drift from real time. Reintegration of a repaired process can be accomplished using a slight modification of the basic algorithm. A similar style algorithm can also be used to achieve synchronization initially.
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4055015
zbMATH Keywords: fault-tolerant algorithm
zbMATH Keywords: clock synchronization
zbMATH Keywords: distributed processes
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90043-0
OpenAlex ID: W1994441984
cites work: On the possibility and impossibility of achieving clock synchronization
cites work: Reaching approximate agreement in the presence of faults
cites work: Time, clocks, and the ordering of events in a distributed system
cites work: Synchronizing clocks in the presence of faults
description: scientific article; zbMATH DE number 4055015