Beyond Lamport's Happened-before: On Time Bounds and the Ordering of Events in Distributed Systems

摘要: The coordination of a sequence actions, to be performed in linear temporal order distributed system, is studied. While asynchronous message-passing systems such ordering events requires the construction message chains based on Lamport's happened-before relation, this no longer true presence time bounds delivery. Given bounds, mere passage can provide information about occurrence at remote sites, without need for explicit confirmation. A new causal structure called centipede introduced, and it shown that centipedes must exist every execution where actions ensured. Centipedes capture subtle interplay between obtained via chains, indirectly derived gained by time, given bounds. are defined using two relations. One syncausality, slight generalisation relation. other novel bound guarantee relation among events, transmission. In precise sense, play role synchronous setting analogous played systems. Our study knowledge-based analysis coordination. Temporally reduced nested knowledge (knowledge knowledge). Obtaining spontaneous event is, turn, require existence an appropriate centipede.