Technical Report CS0522

Title: Lack of Global Clock Does Not Slow Down the Computation in Distributed Networks
Authors: S. Even and S. Rajsbaum
Abstract: The effect of using a simple synchronizer, inspired by marked graphs, on the performance of directed, strongly connected, distributed networks, is analysed. In this paper we assume that the time of message transmission is positive but negligible.

In Section 2 we concentrate on the initialization of the computation, and assume the existence of a global clock but lack of a global start-up signal. It is shown that just the use of the synchronizer guarantees full-rate operation. In fact, no firing-squad mechanism is necessary to reach synchronization. Just the use of the synchronizer guarantees that within 2|V| beats of the clock, including the beat on which the first wake-up message is sent, the network will reach unison, as if there was a global start-up message.

In Section 3 we assume that all local clocks run at the same rate. Again, the use of the synchronizer is sufficient to reach full-rate operation, within 2|V| beats.

In Section 4, no assumption about the local clocks are made. Rates may be different and may not even be fixed. A sluggish clock is such that between two consecutive beats of it, every clock in the network has at least one beat. It is shown that after a trasitory period, the rate of operation of the network is not slower than the rate of any sluggish clock.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1988
To the main CS technical reports page

Computer science department, Technion