|
Abstract : |
Abstmct- Clock synchronization in the presence of faults has been studied extensively in recent years and several software and hardware solutions have been proposed. Software solutions re-quire nodes to exchange and adjust their individual clock values periodically. Since the clock values are exchanged via message passing, the time overhead induced by the software solutions can be substantial, especially if a tight synchronization is de-sired. Hardware solutions, on the other hand, use additional hardware to achieve a very tight synchronization with minimal time overhead. However, the prohibitive cost of the additional hardware limits their usefulness to small systems. In this paper, we propose a synchronization scheme that strikes a balance between the hardware requirement and the clock skews attainable. The proposed scheme is a software al-gorithm that uses minimal additional hardware to achieve rea-sonably tight synchronization. Unlike other software solutions, the guaranteed worst case skews can be made insensitive to the maximum variation of message transit delay in the system. The scheme is particularly suitable for large partially-connected dis-tributed systems with topologies that support simple point-to-point broadcast algorithms. Examples of such topologies include the hypercube and the mesh interconnection structures. Index Terms- Clock skew, distributed systems, hexagonal mesh, hypercube, synchronization., |
