Synchronizers

Two models of computation have been used for the development of distributed algorithms: the synchronous and the asynchronous model. In the synchronous model the execution of an algorithm operates in cycles. The actions of a process in cycle $(i+1)$ depend on its state after cycle $i$ and the messages sent to it in cycle $i$. Note that it is therefore necessary that all messages that are sent to it in cycle $i$ are received before the process starts its computation of cycle $(i+1)$. We can think of the system as if there is a global clock, giving pulses at regular intervals. Computation takes place at clock pulses, and a message, sent in one cycle is guaranteed to be received before the next pulse. In asynchronous model it is assumed that there are no clocks and the message delivery time is not bounded a priori.

The synchronous model is stronger than the asynchronous model. Consequently, distributed algorithms for synchronous networks are more efficient than algorithms for asynchronous networks. Therefore simulation algorithms have been designed to simulate synchronous algorithms on asynchronous networks. These simulation algorithms are called synchronizers. They are inteded to be used as an additional layer of software, transparent to the user, on top of an asynchronous network, so that it can now execute synchronous protocols. Thus, with a synchronizer, the computation proceeds in rounds, trying to simulate the pulse-by-pulse activity of a synchronous protocol. For this purpose, a synchronizer basically generates a sequence of clock pulses at each node of the network satisfying the following property: A new pulse is generated at a node only after it receives all the messages of the synchronous algorithm, sent to that node by its neighbours at previous pulses. Clearly, a synchronizer will require additional messages.

In many practical communication systems the asynchronous model can be strengthened. While it is still true that most systems lack a common clocking mechanism, they do often guarantee message delivery within a fixed (and small) time bound. This is particularly true of the new generation of computer networks, which are comprised of high speed fiber optic lines and in which the messages are routed through specialized high speed hardware rather than in general purpose processors. For this reason Chou introduced a new network model, referred to as Asynchronous Bounded Delay Networks (ABD Networks). This model is weaker than synchronous model but stronger than asynchronous model. It is assumed that processes have local clocks. These clocks run at the same speed, but they are not synchronized. Furthermore a fixed bound on message delivery is assumed.

In ABD Networks, an initial exchange of START messages is required to make every process starts its local clock at approximately the same time. After this intitialization phase a processor will use its clock to decide when the next cycle of the simulated algorithm is executed. The following two requirements must be satisfied:

R1

If a process q sends a message to its neighbour p in some cycle $i$, this message must be received before p simulates cycle $(i+1)$; and

R2

if a process p receives a message it must be possible for p to determine to what cycle this message belongs.

Requirement R1 is obvious because p's actions in cycle $(i+1)$ depend on q's message. Failure to meet the requirement R2 may lead to incorrect simulation.

To compare the speed of synchronizers on an ABD Network we introduce the concept of cycle time. The cycle time of a synchronizer is the time it takes to simulate one cycle of the synchronous algorithm. Chou presented two synchronizers. His first synchronizer has a cycle time of 2. To meet the requirement R2, one bit is added to every message of the simulated algorithm. The synchronizer can be imlemented with $O(1)$ storage per process.The extra bit is avoided in the second synchronizer, but this is paid for with a cycle time of 3. Tel,Zaks and Korach recently presented a synchronizer with a cycle time of 2, without the extra bit. Internal storage needed in a node to implement this synchronizer equals the degree of the node on the network. They also presented similar synchronizers for the more realistic case where the clocks may suffer a -small and bounded- drift.

SEE ALSO: Asynchronous and Archimedean timing, Synchronous timing (Section 4.3.1) and Making new networks (Section 6).