Clock Synchronization in Distributed Systems (Clock Synchronization in Distributed Systems)

From Algorithm Wiki
Jump to navigation Jump to search


The difference between the largest and the smallest clock values among all stations in a Mobile Ad Hoc Network (MANET) is called the maximum clock offset. The goal is to minimize the maximum clock offset.


$n$: number of nodes in network

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
ASP 2005 $O(n)$ $O(n)$ (per node) Exact Deterministic Time
Clock-sampling mutual network synchronization 2007 $O(n)$ $O({1})$? (per node) Exact Deterministic Time
MATSF 2004 $O(n)$ $O(n)$? (per node) Exact Deterministic Time

Time Complexity Graph

Clock Synchronization in Distributed Systems - Time.png