Abstract
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 develop a very robust high-precision clocking system for hardware designs like systems-on-chip for critical applications. It is devoted to the design and the correctness proof of a novel Byzantine fault-tolerant self-stabilizing pulse synchronization protocol, which facilitates a direct implementation in standard asynchronous digital logic. Despite the severe implementation constraints, it offers optimal resilience and smaller complexity than all existing pulse synchronization protocols.
The full paper is available at the arxiv [9]. This work has been supported by the Swiss National Science Foundation (SNSF), by the Austrian Science Foundation (FWF) project FATAL (P21694), and by by the Israeli Science Foundation (ISF) Grant number 1685/07. Danny Dolev is Incumbent of the Berthold Badler Chair.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ben-Or, M., Dolev, D., Hoch, E.N.: Fast self-stabilizing byzantine tolerant digital clock synchronization. In: Proc. 27th symposium on Principles of Distributed Computing (PODC), pp. 385–394 (2008)
Berman, A., Keidar, I.: Low-Overhead Error Detection for Networks-on-Chip. In: The 27th International Conference on Computer Design, ICCD (2009)
Bhamidipati, R., Zaidi, A., Makineni, S., Low, K., Chen, R., Liu, K.Y., Dalgrehn, J.: Challenges and Methodologies for Implementing High-Performance Network Processors. Intel Technology Journal 6(3), 83–92 (2002)
Chapiro, D.M.: Globally-Asynchronous Locally-Synchronous Systems. Ph.D. thesis, Stanford University (1984)
Constantinescu, C.: Trends and Challenges in VLSI Circuit Reliability. IEEE Micro 23(4), 14–19 (2003)
Daliot, A., Dolev, D.: Self-Stabilizing Byzantine Pulse Synchronization. CoRR abs/cs/0608092 (2006)
Daliot, A., Dolev, D., Parnas, H.: Self-Stabilizing Pulse Synchronization Inspired by Biological Pacemaker Networks. In: Huang, S.-T., Herman, T. (eds.) SSS 2003. LNCS, vol. 2704, pp. 32–48. Springer, Heidelberg (2003)
Dike, C., Burton, E.: Miller and Noise Effects in a Synchronizing Flip-Flop. IEEE Journal of Solid-State Circuits SC 34(6), 849–855 (1999)
Dolev, D., Függer, M., Lenzen, C., Schmid, U.: Fault-tolerant Algorithms for Tick-Generation in Asynchronous Logic: Robust Pulse Generation. CoRR abs/cs/1105.4708 (2011)
Dolev, S., Welch, J.L.: Self-stabilizing clock synchronization in the presence of byzantine faults. Journal of the ACM 51(5), 780–799 (2004)
Friedman, E.G.: Clock Distribution Networks in Synchronous Digital Integrated Circuits. Proceedings of the IEEE 89(5), 665–692 (2001)
Fuchs, G., Függer, M., Steininger, A.: On the Threat of Metastability in an Asynchronous Fault-Tolerant Clock Generation Scheme. In: Proc. 15th Symposium on Asynchronous Circuits and Systems (ASYNC), pp. 127–136. Chapel Hill, N. Carolina (2009)
Függer, M.: Analysis of On-Chip Fault-Tolerant Distributed Algorithms. Ph.D. thesis, Technische Universität Wien, Institut für Technische Informatik (2010)
Függer, M., Dielacher, A., Schmid, U.: How to Speed-Up Fault-Tolerant Clock Generation in VLSI Systems-on-Chip via Pipelining. In: Proc. 8th European Dependable Computing Conference (EDCC), pp. 230–239 (2010)
Függer, M., Schmid, U.: Reconciling Fault-Tolerant Distributed Computing and Systems-on-Chip. Research Report 13/2010, Technische Universität Wien, Institut für Technische Informatik (2010)
Függer, M., Schmid, U., Fuchs, G., Kempf, G.: Fault-Tolerant Distributed Clock Generation in VLSI Systems-on-Chip. In: Proc. 6th European Dependable Computing Conference (EDCC), pp. 87–96 (2006)
Gadlage, M.J., Eaton, P.H., Benedetto, J.M., Carts, M., Zhu, V., Turflinger, T.L.: Digital Device Error Rate Trends in Advanced CMOS Technologies. IEEE Transactions on Nuclear Science 53(6), 3466–3471 (2006)
Hoch, E., Dolev, D., Daliot, A.: Self-stabilizing Byzantine Digital Clock Synchronization. In: Datta, A.K., Gradinariu, M. (eds.) SSS 2006. LNCS, vol. 4280, pp. 350–362. Springer, Heidelberg (2006)
Internat. Technology Roadmap for Semiconductors (2007), http://www.itrs.net
Kinniment, D.J., Bystrov, A., Yakovlev, A.V.: Synchronization Circuit Performance. IEEE Journal of Solid-State Circuits SC 37(2), 202–209 (2002)
Malekpour, M.: A Byzantine-Fault Tolerant Self-stabilizing Protocol for Distributed Clock Synchronization Systems. In: Datta, A.K., Gradinariu, M. (eds.) SSS 2006. LNCS, vol. 4280, pp. 411–427. Springer, Heidelberg (2006)
Marino, L.: General Theory of Metastable Operation. IEEE Transactions on Computers C 30(2), 107–115 (1981)
Metra, C., Francescantonio, S., Mak, T.: Implications of Clock Distribution Faults and Issues with Screening them During Manufacturing Testing. IEEE Transactions on Computers 53(5), 531–546 (2004)
Pease, M., Shostak, R., Lamport, L.: Reaching Agreement in the Presence of Faults. Journal of the ACM 27, 228–234 (1980)
Polzer, T., Handl, T., Steininger, A.: A Metastability-Free Multi-synchronous Communication Scheme for SoCs. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol. 5873, pp. 578–592. Springer, Heidelberg (2009)
Portmann, C.L., Meng, T.H.Y.: Supply Noise and CMOS Synchronization Errors. IEEE Journal of Solid-State Circuits SC 30(9), 1015–1017 (1995)
Restle, P.J., et al.: A Clock Distribution Network for Microprocessors. IEEE Journal of Solid-State Circuits 36(5), 792–799 (2001)
Semiat, Y., Ginosar, R.: Timing Measurements of Synchronization Circuits. In: Proc. 9th Symposium on Asynchronous Circuits and Systems, ASYNC (2003)
Srikanth, T.K., Toueg, S.: Optimal Clock Synchronization. Journal of the ACM 34(3), 626–645 (1987)
Sundaresan, K., Allen, P., Ayazi, F.: Process and temperature compensation in a 7-MHz CMOS clock oscillator. IEEE J. Solid-State Circuits 41(2), 433–442 (2006)
Teehan, P., Greenstreet, M., Lemieux, G.: A Survey and Taxonomy of GALS Design Styles. IEEE Design and Test of Computers 24(5), 418–428 (2007)
Widder, J., Schmid, U.: The Theta-Model: Achieving Synchrony without Clocks. Distributed Computing 22(1), 29–47 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dolev, D., Függer, M., Lenzen, C., Schmid, U. (2011). Fault-Tolerant Algorithms for Tick-Generation in Asynchronous Logic: Robust Pulse Generation. In: Défago, X., Petit, F., Villain, V. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2011. Lecture Notes in Computer Science, vol 6976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24550-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-24550-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24549-7
Online ISBN: 978-3-642-24550-3
eBook Packages: Computer ScienceComputer Science (R0)