Technical Report CS0689

Authors: U. Abraham, S. Ben-David, S. Moran
PDF - RevisedCS0689.revised.pdf
Abstract: An ongoing debate among theoreticians of distributed systems concerns the global time issue. The basic question seems to be to what extent does a model with global time reflect the `real' behavior of a distributed system. The assumption of the existence of global time simplifies the analysis of distributed algorithms to an extent that makes it almost irresistible. On the other hand it should be clear that when the operations discussed are of time duration that is comparable to that of the time needed for a signal to pass between different components of the system, then such an assumption is unrealistic. The debate is of a somewhat philosophical nature mainly because, so far, there were no known examples of faulty conclusions caused by excessive use of the global time model. In this note we demonstrate, for the first time, a protocol that is guaranteed to perform well as long as it is run in a system that enjoys the existence of global time, yet it may fail in some other conceivable circumstances. The protocol is very simple and is often used as a basic step in protocols for mutual exclusion. By the results of [5], such a phenomenon could not have occurred had we been running out protocol on one of the three common types of shared registers (safe, regular or atomic). Another contribution of this work is the introduction of a new class of shared memory registers - `weakly regular registers'. Our weak regularity is a natural variant on Lamport's definition of regularity of registers. \newpage
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 1991
To the main CS technical reports page

Computer science department, Technion