Beyond Lamport's happened-before: On time bounds and the ordering of events in distributed systems

Ido Ben-Zvi, Yoram Moses

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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.

שפה מקוריתאנגלית
מספר המאמר13
כתב עתJournal of the ACM
כרך61
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אפר׳ 2014

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2200.2207???
  • ???subjectarea.asjc.1700.1710???
  • ???subjectarea.asjc.1700.1708???
  • ???subjectarea.asjc.1700.1702???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Beyond Lamport's happened-before: On time bounds and the ordering of events in distributed systems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי