{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:51Z","timestamp":1750306851921,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2014,9,8]],"date-time":"2014-09-08T00:00:00Z","timestamp":1410134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"office of the Chief Scientist of the Israeli Ministry of Industry and Trade and Labor"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Le 3107\/1-1"],"award-info":[{"award-number":["Le 3107\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ISG (Israeli Smart Grid) Consortium"},{"name":"Swiss Society of Friends of the Weizmann Institute of Science"},{"name":"Israeli Ministry of Science and Technology","award":["Mar-78"],"award-info":[{"award-number":["Mar-78"]}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["Center No. 4\/11"],"award-info":[{"award-number":["Center No. 4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SIC P26436"},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,9,8]]},"abstract":"<jats:p>Today\u2019s hardware technology presents a new challenge in designing robust systems. Deep submicron VLSI technology introduces transient and permanent faults that were never considered in low-level system designs in the past. Still, robustness of that part of the system is crucial and needs to be guaranteed for any successful product. Distributed systems, on the other hand, have been dealing with similar issues for decades. However, neither the basic abstractions nor the complexity of contemporary fault-tolerant distributed algorithms match the peculiarities of hardware implementations.<\/jats:p>\n          <jats:p>This article is intended to be part of an attempt striving to bridge over this gap between theory and practice for the clock synchronization problem. Solving this task sufficiently well will allow to build an ultra-robust high-precision clocking system for hardware designs like systems-on-chips in critical applications. As our first building block, we describe and prove correct a novel distributed, Byzantine fault-tolerant, probabilistically self-stabilizing pulse synchronization protocol, called FATAL, that can be implemented using standard asynchronous digital logic: Correct FATAL nodes are guaranteed to generate pulses (i.e., unnumbered clock ticks) in a synchronized way, despite a certain fraction of nodes being faulty. FATAL uses randomization only during stabilization and, despite the strict limitations introduced by hardware designs, offers optimal resilience and smaller complexity than all existing protocols. Finally, we show how to leverage FATAL to efficiently generate synchronized, self-stabilizing, high-frequency clocks.<\/jats:p>","DOI":"10.1145\/2560561","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T14:39:29Z","timestamp":1410273569000},"page":"1-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Fault-tolerant algorithms for tick-generation in asynchronous logic"],"prefix":"10.1145","volume":"61","author":[{"given":"Danny","family":"Dolev","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"F\u00fcgger","sequence":"additional","affiliation":[{"name":"Vienna University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Schmid","sequence":"additional","affiliation":[{"name":"Vienna University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Lenzen","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400793"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400802"},{"key":"e_1_2_1_4_1","first-page":"83","article-title":"Challenges and methodologies for implementing high-performance network processors","volume":"6","author":"Bhamidipati R.","year":"2002","unstructured":"Bhamidipati , R. , Zaidi , A. , Makineni , S. , Low , K. , Chen , R. , Liu , K.-Y. , and Dalgrehn , J. 2002 . Challenges and methodologies for implementing high-performance network processors . Intel Technol. J. 6 , 3, 83 -- 92 . Bhamidipati, R., Zaidi, A., Makineni, S., Low, K., Chen, R., Liu, K.-Y., and Dalgrehn, J. 2002. Challenges and methodologies for implementing high-performance network processors. Intel Technol. J. 6, 3, 83--92.","journal-title":"Intel Technol. J."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00151-X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2003.1225959"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Daliot A. and Dolev D. 2006. Self-stabilizing byzantine pulse synchronization. Comput. Res. Repository abs\/cs\/0608092.  Daliot A. and Dolev D. 2006. Self-stabilizing byzantine pulse synchronization. Comput. Res. Repository abs\/cs\/0608092.","DOI":"10.1145\/1146381.1146405"},{"volume-title":"Proceedings of the SSS. 32--48","author":"Daliot A.","key":"e_1_2_1_9_1","unstructured":"Daliot , A. , Dolev , D. , and Parnas , H . 2003. Self-stabilizing pulse synchronization inspired by biological pacemaker networks . In Proceedings of the SSS. 32--48 . Daliot, A., Dolev, D., and Parnas, H. 2003. Self-stabilizing pulse synchronization inspired by biological pacemaker networks. In Proceedings of the SSS. 32--48."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Dike C. and Burton E. 1999. Miller and noise effects in a synchronizing flip-flop. IEEE J. Solid-State Circ. SC-34 6 849--855.  Dike C. and Burton E. 1999. Miller and noise effects in a synchronizing flip-flop. IEEE J. Solid-State Circ. SC-34 6 849--855.","DOI":"10.1109\/4.766819"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90004-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.01.001"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS).","volume":"4280","author":"Dolev D.","unstructured":"Dolev , D. and Hoch , E . 2007. Byzantine self-stabilizing pulse in a bounded-delay model . In Proceedings of the 9th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Vol. 4280 , 350--362. Dolev, D. and Hoch, E. 2007. Byzantine self-stabilizing pulse in a bounded-delay model. In Proceedings of the 9th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Vol. 4280, 350--362."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5931"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017463"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/323596.323602"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.929649"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASYNC.2009.15"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/EDCC.2010.35"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0151-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/EDCC.2006.11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNS.2006.886212"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 8th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201906)","volume":"4280","author":"Hoch E.","unstructured":"Hoch , E. , Dolev , D. , and Daliot , A . 2006. Self-stabilizing byzantine digital clock synchronization . In Proceedings of the 8th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201906) . Vol. 4280 , 350--362. Hoch, E., Dolev, D., and Daliot, A. 2006. Self-stabilizing byzantine digital clock synchronization. In Proceedings of the 8th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201906). Vol. 4280, 350--362."},{"key":"e_1_2_1_26_1","unstructured":"International Technology Roadmap for Semiconductors 2012. International Technology Roadmap for Semiconductors. http:\/\/www.itrs.net.  International Technology Roadmap for Semiconductors 2012. International Technology Roadmap for Semiconductors. http:\/\/www.itrs.net."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Kinniment D. J. Bystrov A. and Yakovlev A. V. 2002. Synchronization circuit performance. IEEE J. Solid-State Circ. SC-37 2 202--209.  Kinniment D. J. Bystrov A. and Yakovlev A. V. 2002. Synchronization circuit performance. IEEE J. Solid-State Circ. SC-37 2 202--209.","DOI":"10.1109\/4.982426"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835799"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667057"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80033-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759076.1759107"},{"key":"e_1_2_1_32_1","unstructured":"Malekpour M. 2009. A self-stabilizing Byzantine-fault-tolerant clock synchronization protocol. Tech. rep. TM-2009-215758 NASA.  Malekpour M. 2009. A self-stabilizing Byzantine-fault-tolerant clock synchronization protocol. Tech. rep. TM-2009-215758 NASA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1963635.1963638"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.1275295"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05118-0_40"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Portmann C. L. and Meng T. H. Y. 1995. Supply noise and CMOS synchronization errors. IEEE J. Solid-State Circ. SC-30 9 1015--1017.  Portmann C. L. and Meng T. H. Y. 1995. Supply noise and CMOS synchronization errors. IEEE J. Solid-State Circ. SC-30 9 1015--1017.","DOI":"10.1109\/4.406400"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.918917"},{"volume-title":"Proceedings of the 9th Symposium on Asynchronous Circuits and Systems (ASYNC). 68--77","author":"Semiat Y.","key":"e_1_2_1_39_1","unstructured":"Semiat , Y. and Ginosar , R . 2003. Timing measurements of synchronization circuits . In Proceedings of the 9th Symposium on Asynchronous Circuits and Systems (ASYNC). 68--77 . Semiat, Y. and Ginosar, R. 2003. Timing measurements of synchronization circuits. In Proceedings of the 9th Symposium on Asynchronous Circuits and Systems (ASYNC). 68--77."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28876"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2005.863149"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2007.151"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0080-x"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2560561","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2560561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:21Z","timestamp":1750234221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2560561"}},"subtitle":["Robust pulse generation"],"short-title":[],"issued":{"date-parts":[[2014,9,8]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9,8]]}},"alternative-id":["10.1145\/2560561"],"URL":"https:\/\/doi.org\/10.1145\/2560561","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,9,8]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}