Abstract
This thesis deals with the synchronization of phases of digital clocks or periodic events in a distributed system which has a ring topology. The clocks considered are bounded and synchronous i.e., run at the same rate. And if some periodic event with multiple phases is being considered then it is assumed that the phases of the event are of equal duration. The model assumes that the system can be in any arbitrary state initially and will be brought to a synchronized state within a finite number of steps without any external aid or interference (i.e., self-stabilizing). The processors are identical to each other. The protocol is an example of pure distributed control. The problem tackled herein is of 2'-phase synchronization, where i is any positive integer. First, it is proved that it is impossible to have a deterministic algorithm which can synchronize a system of binary phase clocks or events with uniform pro cessors without using auxiliary variables and which is valid for variable ring sizes (i.e., retain the property of scalability). Second, a distributed self-stabilizing algorithm for binary phase synchronization which uses auxiliary variables is developed together with its proof of correctness for rings with odd number of processors. The worst case synchronization time of the algortihm is [ ] pulses, where n is the size of the ring. Finally, this tecnique is extended to achieve synchronization of 2i-phase clocks or events.
Pancholi, Alok (1994). Self-stabilizing clock phase synchronization in a distributed ring. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1994 -THESIS -P1884.