research-article

Open access

Fault-tolerant algorithms for tick-generation in asynchronous logic: Robust pulse generation

Authors:

Matthias Függer,

Christoph LenzenAuthors Info & Claims

Journal of the ACM (JACM), Volume 61, Issue 5

Article No.: 30, Pages 1 - 74

https://doi.org/10.1145/2560561

Published: 08 September 2014 Publication History

Abstract

Today’s 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.

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.

References

[1]

Ajtai, M., Komlós, J., and Szemerédi, E. 1983. An O(n log n) sorting network. In Proceedings of the 15th Symposium on Theory of Computing (STOC). 1--9.

Digital Library

[2]

Attiya, H. and Censor, K. 2008. Lower bounds for randomized consensus under a weak adversary. In Proceedings of the 27th Symposium on Principles of Distributed Computing (PODC). 315--324.

Digital Library

[3]

Ben-Or, M., Dolev, D., and Hoch, E. N. 2008. Fast self-stabilizing byzantine tolerant digital clock synchronization. In Proceedings of the 27th Symposium on Principles of Distributed Computing (PODC). 385--394.

Digital Library

[4]

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.

[5]

Biaz, S. and Welch, J. 2001. Closed form bounds for clock synchronization under simple uncertainty assumptions. Inf. Process. Lett. 80, 3, 151--157.

Digital Library

[6]

Chapiro, D. M. 1984. Globally-asynchronous locally-synchronous systems. Ph.D. thesis, Stanford University.

Digital Library

[7]

Constantinescu, C. 2003. Trends and challenges in VLSI circuit reliability. IEEE Micro 23, 4, 14--19.

Digital Library

[8]

Daliot, A. and Dolev, D. 2006. Self-stabilizing byzantine pulse synchronization. Comput. Res. Repository abs/cs/0608092.

[9]

Daliot, A., Dolev, D., and Parnas, H. 2003. Self-stabilizing pulse synchronization inspired by biological pacemaker networks. In Proceedings of the SSS. 32--48.

Digital Library

[10]

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.

[11]

Dolev, D. 1982. The Byzantine generals strike again. J. Algor. 3, 14--30.

[12]

Dolev, D., Fuegger, M., Lenzen, C., Posch, M., Schmid, U., and Steininger, A. 2014. Rigorously modeling self-stabilizing fault-tolerant circuits: An ultra-robust clocking scheme for systems-on-chip. J. Comput. Syst. Sci. 80, 4, 860--900.

Digital Library

[13]

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.

Digital Library

[14]

Dolev, D., Lynch, N. A., Pinter, S. S., Stark, E. W., and Weihl, W. E. 1986. Reaching approximate agreement in the presence of faults. J. ACM 33, 499--516.

Digital Library

[15]

Dolev, S. and Welch, J. L. 2004. Self-stabilizing clock synchronization in the presence of Byzantine faults. J. ACM 51, 5, 780--799.

Digital Library

[16]

Fischer, M. J. and Lynch, N. A. 1982. A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14, 183--186.

[17]

Fischer, M. J., Lynch, N. A., and Merritt, M. 1985. Easy impossibility proofs for distributed consensus problems. In Proceedings of the 4th Conference of Principles of Distributed Computing (PODC). 59--70.

Digital Library

[18]

Friedman, E. G. 2001. Clock distribution networks in synchronous digital integrated circuits. Proc. IEEE 89, 5, 665--692.

[19]

Fuchs, G., Függer, M., and Steininger, A. 2009. On the threat of metastability in an asynchronous fault-tolerant clock generation scheme. In Proceedings of the 15th Symposium on Asynchronous Circuits and Systems (ASYNC) (Chapel Hill, N. Carolina). 127--136.

Digital Library

[20]

Függer, M. 2010. Analysis of on-chip fault-tolerant distributed algorithms. Ph.D. thesis, Technische Universität Wien, Institut für Technische Informatik.

[21]

Függer, M., Dielacher, A., and Schmid, U. 2010. How to speed-up fault-tolerant clock generation in VLSI systems-on-chip via pipelining. In Proceedings of the 8th European Dependable Computing Conference (EDCC). 230--239.

Digital Library

[22]

Függer, M. and Schmid, U. 2012. Reconciling fault-tolerant distributed computing and systems-on-chip. Distrib. Comput. 24, 6, 323--355.

Digital Library

[23]

Függer, M., Schmid, U., Fuchs, G., and Kempf, G. 2006. Fault-tolerant distributed clock generation in VLSI systems-on-chip. In Proceedings of the 6th European Dependable Computing Conference (EDCC). 87--96.

Digital Library

[24]

Gadlage, M. J., Eaton, P. H., Benedetto, J. M., Carts, M., Zhu, V., and Turflinger, T. L. 2006. Digital device error rate trends in advanced CMOS technologies. IEEE Trans. Nuclear Sci. 53, 6, 3466--3471.

[25]

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’06). Vol. 4280, 350--362.

Digital Library

[26]

International Technology Roadmap for Semiconductors 2012. International Technology Roadmap for Semiconductors. http://www.itrs.net.

[27]

Kinniment, D. J., Bystrov, A., and Yakovlev, A. V. 2002. Synchronization circuit performance. IEEE J. Solid-State Circ. SC-37, 2, 202--209.

[28]

Kuhn, F., Lenzen, C., Locher, T., and Oshman, R. 2010. Optimal gradient clock synchronization in dynamic networks. In Proceedings of the 29th Symposium on Principles of Distributed Computing (PODC).

Digital Library

[29]

Lenzen, C., Locher, T., and Wattenhofer, R. 2010. Tight bounds for clock synchronization. In J. ACM 57, 2.

Digital Library

[30]

Lundelius, J. and Lynch, N. 1984. An upper and lower bound for clock synchronization. Inf. Control 62, 2--3, 190--204.

[31]

Malekpour, M. 2006. A Byzantine-fault tolerant self-stabilizing protocol for distributed clock synchronization systems. In Proceedings of the 9th Conference on Stabilization, Safety, and Security of Distributed Systems (SSS). 411--427.

Digital Library

[32]

Malekpour, M. 2009. A self-stabilizing Byzantine-fault-tolerant clock synchronization protocol. Tech. rep., TM-2009-215758, NASA.

[33]

Marino, L. 1981. General theory of metastable operation. IEEE Trans. Comput. C-30, 2, 107--115.

Digital Library

[34]

Metra, C., Francescantonio, S., and Mak, T. 2004. Implications of clock distribution faults and issues with screening them during manufacturing testing. IEEE Trans. Comput. 53, 5, 531--546.

Digital Library

[35]

Pease, M., Shostak, R., and Lamport, L. 1980. Reaching agreement in the presence of faults. J. ACM 27, 228--234.

Digital Library

[36]

Polzer, T., Handl, T., and Steininger, A. 2009. A metastability-free multi-synchronous communication scheme for SoCs. In Proceedings of the 11th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). 578--592.

Digital Library

[37]

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.

[38]

Restle, P., McNamara, T., Webber, D., Camporese, P., Eng, K., Jenkins, K., Allen, D., Rohn, M., Quaranta, M., Boerstler, D., Alpert, C., Carter, C., Bailey, R., Petrovick, J., Krauter, B., and McCredie, B. 2001. A clock distribution network for microprocessors. IEEE J. Solid-State Circ. 36, 5, 792--799.

[39]

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.

Digital Library

[40]

Srikanth, T. K. and Toueg, S. 1987. Optimal clock synchronization. J. ACM 34, 3, 626--645.

Digital Library

[41]

Sundaresan, K., Allen, P., and Ayazi, F. 2006. Process and temperature compensation in a 7-MHz CMOS clock oscillator. IEEE J. Solid-State Circ. 41, 2, 433--442.

[42]

Teehan, P., Greenstreet, M., and Lemieux, G. 2007. A survey and taxonomy of GALS design styles. IEEE Des. Test Comput. 24, 5, 418--428.

Digital Library

[43]

Widder, J. and Schmid, U. 2009. The theta-model: Achieving synchrony without clocks. Distrib. Comput. 22, 1, 29--47.

Digital Library

Cited By

Bund JFügger MMedina M(2023)PALS: Distributed Gradient Clocking on ChipIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.331117831:11(1740-1753)Online publication date: Dec-2023
https://doi.org/10.1109/TVLSI.2023.3311178
Függer MLenzen CSchmid U(2022)On Specifications and Proofs of Timed CircuitsPrinciples of Systems Design10.1007/978-3-031-22337-2_6(107-130)Online publication date: 29-Dec-2022
https://doi.org/10.1007/978-3-031-22337-2_6
Yu SZhu JYang J(2021)Efficient Two-Dimensional Self-Stabilizing Byzantine Clock Synchronization in WALDEN2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00096(723-730)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00096
Show More Cited By

Index Terms

Fault-tolerant algorithms for tick-generation in asynchronous logic: Robust pulse generation
1. Hardware
  1. Hardware test
  2. Robustness
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Fault Tolerant Gradient Clock Synchronization
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems, and the optimal achievable local skew in general fault-free networks. However, so far nothing non-trivial is known about the ...
Fault-tolerant algorithms for tick-generation in asynchronous logic: robust pulse generation
SSS'11: Proceedings of the 13th international conference on Stabilization, safety, and security of distributed systems

The advances of deep submicron VLSI technology pose new challenges in designing robust systems, which can in principle be addressed by approaches established in fault-tolerant distributed systems research. This paper is the first step in an attempt to ...
A Byzantine-fault tolerant self-stabilizing protocol for distributed clock synchronization systems
SSS'06: Proceedings of the 8th international conference on Stabilization, safety, and security of distributed systems

Embedded distributed systems have become an integral part of safety-critical computing applications, necessitating system designs that incorporate fault tolerant clock synchronization in order to achieve ultra-reliable assurance levels. Many efficient ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 61, Issue 5

August 2014

171 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2668245

Editor:
Victor Vianu
University of California, San Diego

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 September 2014

Accepted: 01 December 2013

Revised: 01 May 2013

Received: 01 March 2012

Published in JACM Volume 61, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

office of the Chief Scientist of the Israeli Ministry of Industry and Trade and Labor
Deutsche Forschungsgemeinschaft
Austrian Science Fund
ISG (Israeli Smart Grid) Consortium
Swiss Society of Friends of the Weizmann Institute of Science
Israeli Ministry of Science and Technology
Israeli Centers for Research Excellence
SIC P26436
Swiss National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
834
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)9

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bund JFügger MMedina M(2023)PALS: Distributed Gradient Clocking on ChipIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.331117831:11(1740-1753)Online publication date: Dec-2023
https://doi.org/10.1109/TVLSI.2023.3311178
Függer MLenzen CSchmid U(2022)On Specifications and Proofs of Timed CircuitsPrinciples of Systems Design10.1007/978-3-031-22337-2_6(107-130)Online publication date: 29-Dec-2022
https://doi.org/10.1007/978-3-031-22337-2_6
Yu SZhu JYang J(2021)Efficient Two-Dimensional Self-Stabilizing Byzantine Clock Synchronization in WALDEN2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00096(723-730)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00096
Lenzen CWiederhake B(2020)Brief Announcement: TRIX: Low-Skew Pulse Propagation for Fault-Tolerant HardwareStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_23(295-300)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64348-5_23
Lenzen CRybicki J(2019)Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as ConsensusJournal of the ACM10.1145/333947166:5(1-56)Online publication date: 17-Aug-2019
https://dl.acm.org/doi/10.1145/3339471
Khanchandani PLenzen C(2019)Self-Stabilizing Byzantine Clock Synchronization with Optimal PrecisionTheory of Computing Systems10.1007/s00224-017-9840-363:2(261-305)Online publication date: 15-May-2019
https://dl.acm.org/doi/10.1007/s00224-017-9840-3
Perner MSchmid U(2018)Self-Stabilizing High-Speed Communication in Multi-Synchronous GALS Architectures2018 IEEE 24th International Symposium on On-Line Testing And Robust System Design (IOLTS)10.1109/IOLTS.2018.8474221(157-164)Online publication date: Jul-2018
https://doi.org/10.1109/IOLTS.2018.8474221
Fugger MNowak TSchmid U(2016)Unfaithful Glitch Propagation in Existing Binary Circuit ModelsIEEE Transactions on Computers10.1109/TC.2015.243579165:3(964-978)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1109/TC.2015.2435791
Dolev DFügger MLenzen CPerner MSchmid U(2016)HEX: Scaling honeycombs is easier than scaling clock treesJournal of Computer and System Sciences10.1016/j.jcss.2016.03.00182:5(929-956)Online publication date: Aug-2016
https://doi.org/10.1016/j.jcss.2016.03.001
Khanchandani PLenzen C(2016)Self-stabilizing Byzantine Clock Synchronization with Optimal PrecisionStabilization, Safety, and Security of Distributed Systems10.1007/978-3-319-49259-9_18(213-230)Online publication date: 3-Nov-2016
https://doi.org/10.1007/978-3-319-49259-9_18
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents