Consider a complete communication network on n nodes, each of which is a state machine with s states. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are "odd" and which are "even". We require that the solution is self-stabilising (reaching the correct operation from any initial state) and it tolerates f Byzantine failures (nodes that send arbitrary misinformation). Prior algorithms are expensive to implement in hardware: they require a source of random bits or a large number of states s. We use computational techniques to construct very compact deterministic algorithms for the first non-trivial case of f = 1. While no algorithm exists for n ＜ 4, we show that as few as 3 states are sufficient for all values n ≥ 4. We prove that the problem cannot be solved with only 2 states for n = 4, but there is a 2-state solution for all values n ≥ 6.
展开▼
机译：考虑在n个节点上的完整通信网络，每个节点都是具有s个状态的状态机。在同步2计数中，节点接收一个公共时钟脉冲，它们必须就哪些脉冲“奇数”和哪些“偶数”达成一致。我们要求解决方案是自稳定的（从任何初始状态都达到正确的操作），并且它可以容忍f拜占庭式故障（发送任意错误信息的节点）。现有的算法在硬件中实现起来很昂贵：它们需要一个随机位或大量状态s的源。我们使用计算技术为f = 1的第一个非平凡情况构造了非常紧凑的确定性算法。尽管对于n ＜4，不存在任何算法，但我们证明，对于所有n≥4的值，只有3个状态就足够了。 n = 4时，只有2个状态不能解决问题，但是对于所有值n≥6，都有2个状态的解决方案。
展开▼
