Fault-tolerant algorithms for tick-generation in asynchronous logic
Fault-tolerant algorithms for tick-generation in asynchronous logic
复制标题
异步逻辑中刻度生成的容错算法
DOI：
10.1145/2560561
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ulrich Schmid
中科院分区：
文献类型：
--
作者：
Danny Dolev;Matthias Függer;Christoph Lenzen;Ulrich Schmid
今天的硬件技术在设计鲁棒系统方面提出了新的挑战。深亚微米超大规模集成电路技术引入了过去在低层系统设计中从未考虑过的瞬时和永久故障。尽管如此，系统的这一部分的鲁棒性是至关重要的，需要为任何成功的产品提供保证。另一方面，分布式系统几十年来一直在处理类似的问题。然而，无论是基本的抽象，也不是当代容错分布式算法的复杂性匹配的特殊性的硬件implementation.This文章的目的是努力弥合理论和实践之间的差距的时钟同步问题的尝试的一部分。充分解决这一任务将允许为关键应用中的片上系统等硬件设计构建超鲁棒的高精度时钟系统。作为我们的第一个构建块，我们描述并证明了一种新的分布式，拜占庭容错，概率自稳定脉冲同步协议，称为FATAL，可以使用标准异步数字逻辑实现：保证正确的FATAL节点生成脉冲（即，未编号的时钟滴答声），尽管有一定比例的节点发生故障。FATAL仅在稳定期间使用随机化，尽管硬件设计引入了严格的限制，但它提供了最佳的弹性和比所有现有协议更小的复杂性。最后，我们将展示如何利用FATAL来有效地生成同步的、自稳定的高频时钟。
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.
登录
查看更多内容
DOI：
10.1145/1667053.1667057
发表时间：
2010
期刊：
J. ACM
影响因子：
--
作者：
C. Lenzen;Thomas Locher;Roger Wattenhofer
通讯作者：
C. Lenzen;Thomas Locher;Roger Wattenhofer
DOI：
10.1109/4.982426
发表时间：
2002-08
期刊：
IEEE J. Solid State Circuits
影响因子：
--
作者：
D. Kinniment;A. Bystrov;A. Yakovlev
通讯作者：
D. Kinniment;A. Bystrov;A. Yakovlev
时钟分配故障的影响以及在制造测试期间对其进行筛选的问题
影响因子：
3.7
作者：
C. Metra;Stefano Di Francescantonio;T. M. Mak
通讯作者：
T. M. Mak
关于异步容错时钟生成方案中亚稳态的威胁
DOI：
10.1109/async.2009.15
发表时间：
2009
期刊：
2009 15th IEEE Symposium on Asynchronous Circuits and Systems
影响因子：
--
作者：
Gottfried Fuchs;Matthias Függer;A. Steininger
通讯作者：
A. Steininger
影响因子：
1.3
作者：
Matthias Függer;U. Schmid
通讯作者：
U. Schmid