Using simple diffusion to synchronize the clocks in a distributed system

Simple diffusion consists in propagating some data or computation to every unit in a network by spreading it from one unit to its neighbors, which in their turn spread it to the neighbors until every unit is reached. Simple diffusion is easy to implement, scalable, robust with respect to omission faults, and privileges local communication (i.e., uses only links whose cost is the lowest in terms of time needed and/or traffic generated). A solution to the problem of keeping synchronized all the clocks in a large distributed system is presented, that is based on simple diffusion. The traffic generated is O(N), where N is the number of units in the network. The attainable precision is O(d*ε) where ε is the precision with which a unit can synchronize its clock with that of a neighbor, and d is the maximum distance between a unit and the nearest reference clock