{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:40:44Z","timestamp":1766137244411,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T00:00:00Z","timestamp":1566000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["716562"],"award-info":[{"award-number":["716562"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"H2020 Marie Sk?odowska-Curie Actions","award":["754411"],"award-info":[{"award-number":["754411"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the\n            <jats:italic>n<\/jats:italic>\n            nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to\n            <jats:italic>f<\/jats:italic>\n            &lt;\n            <jats:italic>n<\/jats:italic>\n            \/3 ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner.\n          <\/jats:p>\n          <jats:p>\n            Compared to prior work, we achieve\n            <jats:italic>exponential<\/jats:italic>\n            improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem:\n          <\/jats:p>\n          <jats:p>\n            \u2022 In the deterministic setting, the state-of-the-art solutions stabilise in time \u0398 (\n            <jats:italic>f<\/jats:italic>\n            ) and have each node broadcast \u0398(\n            <jats:italic>f<\/jats:italic>\n            log\n            <jats:italic>f<\/jats:italic>\n            ) bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to \u0398 (log\n            <jats:italic>f<\/jats:italic>\n            ) while retaining the same stabilisation time.\n          <\/jats:p>\n          <jats:p>\n            \u2022 In the randomised setting, the state-of-the-art solutions stabilise in time \u0398(\n            <jats:italic>f<\/jats:italic>\n            ) and have each node broadcast\n            <jats:italic>O<\/jats:italic>\n            (1) bits per time unit. We exponentially reduce the stabilisation time to polylog\n            <jats:italic>f<\/jats:italic>\n            while each node broadcasts polylog\n            <jats:italic>f<\/jats:italic>\n            bits per time unit.\n          <\/jats:p>\n          <jats:p>\n            These results are obtained by means of a recursive approach reducing the above task of\n            <jats:italic>self-stabilising<\/jats:italic>\n            pulse synchronisation in the\n            <jats:italic>bounded-delay<\/jats:italic>\n            model to\n            <jats:italic>non-self-stabilising<\/jats:italic>\n            binary consensus in the\n            <jats:italic>synchronous<\/jats:italic>\n            model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.\n          <\/jats:p>","DOI":"10.1145\/3339471","type":"journal-article","created":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T19:41:32Z","timestamp":1566243692000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus"],"prefix":"10.1145","volume":"66","author":[{"given":"Christoph","family":"Lenzen","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6432-6646","authenticated-orcid":false,"given":"Joel","family":"Rybicki","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology Austria (IST Austria), Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00100-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400802"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63511"},{"volume-title":"Perry","year":"1992","author":"Berman Piotr","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760548.1760551"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90004-9"},{"volume-title":"Proceedings of the 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201907)","author":"Dolev Danny","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214112"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/9128.9132"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5931"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2560561"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.09.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Shlomi Dolev. 2000. Self-Stabilization. Cambridge MA   Shlomi Dolev. 2000. Self-Stabilization. Cambridge MA","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017463"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01783662"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790187084"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49259-9_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989732"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2457"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49259-9_21"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2013.97"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M107877X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80033-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Michel Raynal. 2010. Fault-Tolerant Agreement in Synchronous Message-Passing Systems. Morgan 8 Claypool  Michel Raynal. 2010. Fault-Tolerant Agreement in Synchronous Message-Passing Systems. Morgan 8 Claypool","DOI":"10.1007\/978-3-031-02001-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28876"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90043-0"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3339471","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3339471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:08Z","timestamp":1750204448000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3339471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,17]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3339471"],"URL":"https:\/\/doi.org\/10.1145\/3339471","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2019,8,17]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}