{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:36Z","timestamp":1750306836217,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T00:00:00Z","timestamp":1396310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1339\/05 and 1520\/11"],"award-info":[{"award-number":["1339\/05 and 1520\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Arlene & Arnold Goldstein Center at the Technion's autonomous systems program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2542181","type":"journal-article","created":{"date-parts":[[2014,4,22]],"date-time":"2014-04-22T13:37:45Z","timestamp":1398173865000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Beyond Lamport's\n            <i>Happened-before<\/i>"],"prefix":"10.1145","volume":"61","author":[{"given":"Ido","family":"Ben-Zvi","sequence":"first","affiliation":[{"name":"Technion\u2014Israel Institute of Technology, Israel"}]},{"given":"Yoram","family":"Moses","sequence":"additional","affiliation":[{"name":"Technion Israel Institute of Technology, Israel"}]}],"member":"320","published-online":{"date-parts":[[2014,4,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176343654"},{"key":"e_1_2_1_2_1","volume-title":"Linked: The New Science of Networks","author":"Barab\u00e1si A. L.","year":"2002","edition":"1"},{"volume-title":"Proceedings of the 24th International Conference on Distributed Computing (DISC). 421--436","author":"Ben-Zvi I.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000378.2000397"},{"key":"e_1_2_1_5_1","first-page":"3","article-title":"On interactive knowledge with bounded communication","volume":"21","author":"Ben-Zvi I.","year":"2011","journal-title":"J. Appl. Non-Class. Logics"},{"volume-title":"Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge. K. Lodaya and R. Ramanujam, Eds., 29--38","author":"Ben-Zvi I.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 5th Indian Conference on Logic and Its Applications, 5th Indian Conference. K. Lodaya Ed., 97--108","author":"Ben-Zvi I.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01843569"},{"key":"e_1_2_1_9_1","unstructured":"H. H. Clark and C. R. Marshall. 1981. Definite reference and mutual knowledge. In Elements of Discourse Understanding A. K. Joshi B. L. Webber and I. Sag Eds. Cambridge University Press Cambridge UK 10--63.  H. H. Clark and C. R. Marshall. 1981. Definite reference and mutual knowledge. In Elements of Discourse Understanding A. K. Joshi B. L. Webber and I. Sag Eds. Cambridge University Press Cambridge UK 10--63."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"R. Fagin J. Y. Halpern Y. Moses and M. Y. Vardi. 2003. Reasoning about Knowledge. MIT Press Cambridge MA.   R. Fagin J. Y. Halpern Y. Moses and M. Y. Vardi. 2003. Reasoning about Knowledge. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"volume-title":"Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge. K. Lodaya and R. Ramanujam, Eds., 79--93","author":"Goczarowski Y.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1086\/225469"},{"volume-title":"Syntax and semantics","author":"Grice H.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79161"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153770"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_2_1_19_1","unstructured":"H. Kopetz. 2011. Real-Time Systems: Design Principles for Distributed Embedded Applications. 2nd Ed. Springer Science&plus; Business Media.   H. Kopetz. 2011. Real-Time Systems: Design Principles for Distributed Embedded Applications. 2nd Ed. Springer Science&plus; Business Media."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401945"},{"volume-title":"Proceedings of the 5th Conference on Theoretical Aspects of Reasoning about Knowledge. Morgan Kaufmann, 267--283","author":"Krasucki P. J.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993.2994"},{"volume-title":"Convention, A Philosophical Study","year":"1969","author":"Lewis D.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","unstructured":"N. A. Lynch. 1996. Distributed Algorithms. Morgan-Kaufmann.   N. A. Lynch. 1996. Distributed Algorithms. Morgan-Kaufmann."},{"key":"e_1_2_1_26_1","unstructured":"J. McCarthy and P. J. Hayes. 1969. Some philosophical problems from the standpoint of artificial intelligence. In Machine Intelligence 4 D. Michie Ed. Edinburgh University Press 463--502.  J. McCarthy and P. J. Hayes. 1969. Some philosophical problems from the standpoint of artificial intelligence. In Machine Intelligence 4 D. Michie Ed. Edinburgh University Press 463--502."},{"key":"e_1_2_1_27_1","first-page":"60","article-title":"The Small World","volume":"2","author":"Milgram S.","year":"1967","journal-title":"Problem. Psychol. Today"},{"volume-title":"Proceedings of the 4th Conference on Theoretical Aspects of Reasoning about Knowledge (TARK'92)","year":"1992","author":"Moses Y.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198113"},{"key":"e_1_2_1_30_1","unstructured":"M. Osborne and A. Rubinstein. 1994. A Course in Game Theory. MIT Press Cambridge MA.  M. Osborne and A. Rubinstein. 1994. A Course in Game Theory. MIT Press Cambridge MA."},{"volume-title":"Logic from Computer Science, MSRI Publication No. 21","author":"Parikh R.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02811342"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195466"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"H. van Ditmarsch W. van der Hoek and B. Kooi. 2007. Dynamic Epistemic Logic. Springer Publishing Company Inc.   H. van Ditmarsch W. van der Hoek and B. Kooi. 2007. Dynamic Epistemic Logic. Springer Publishing Company Inc.","DOI":"10.1007\/978-1-4020-5839-4"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542181","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2542181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:56Z","timestamp":1750234196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542181"}},"subtitle":["On Time Bounds and the Ordering of Events in Distributed Systems"],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1145\/2542181"],"URL":"https:\/\/doi.org\/10.1145\/2542181","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,4]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}