Beyond Lamport's $\textit{Happened-before}:$ On Time Bounds and the Ordering of Events in Distributed SystemsBeyond Lamport's $\textit{Happened-before}:$ On Time Bounds and the Ordering of Events in Distributed Systems

Access Restriction
Subscribed

 Author Ben-Zvi, Ido ♦ Moses, Yoram Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Distributed computing ♦ Coordination ♦ Knowledge ♦ Real-time systems ♦ Temporal order Abstract The coordination of a sequence of actions, to be performed in a linear temporal order in a distributed system, is studied. While in asynchronous message-passing systems such ordering of events requires the construction of message chains based on Lamport's happened-before relation, this is no longer true in the presence of time bounds on message delivery. Given such bounds, the mere passage of time can provide information about the occurrence of events at remote sites, without the need for explicit confirmation. A new causal structure called the centipede is introduced, and it is shown that centipedes must exist in every execution where linear ordering of actions is ensured. Centipedes capture the subtle interplay between the explicit information obtained via message chains, and the indirectly derived information gained by the passage of time, given the time bounds. Centipedes are defined using two relations. One is called syncausality, a slight generalisation of the happened-before relation. The other is a novel bound guarantee relation among events, that is based on the bounds on message transmission. In a precise sense, centipedes play a role in the synchronous setting analogous to that played by message chains in asynchronous systems. Our study is based on a knowledge-based analysis of distributed coordination. Temporally linear coordination is reduced to nested knowledge (knowledge about knowledge). Obtaining nested knowledge of a spontaneous event is, in turn, shown to require the existence of an appropriate centipede. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 2 Page Count 26 Starting Page 1 Ending Page 26

Open content in new tab

Source: ACM Digital Library