Clock Synchronization in Distributed Systems

Description

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.

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff