Byzantine-Tolerant Phase Clock

doi:10.4230/LIPIcs.OPODIS.2025.30

Byzantine-Tolerant Phase Clock

2026-01-01

0

PRE

AI

Dariusz R. Kowalski *

DOI：10.4230/LIPIcs.OPODIS.2025.30

原文链接

原文求助

摘要

En 中文

相时钟是一种基本的同步机制，用于保持分布式节点紧密同步以执行分布式算法的同一阶段。相时钟通常通过一个本地逻辑计数器实现，该计数器跟踪当前阶段计数。相时钟在群体协议中对于实现领导选举和多数选择特别有用。我们研究了能够容忍拜占庭故障的相时钟。我们证明存在一种相时钟，能够容忍最多f < n/3个故障节点（n为节点数），其本地计数器值的差距为O(n² log n)。当f ≤ n/8时，该差距可进一步降低至O(log n)。我们还证明，如果f > n/3，则随着时间推移，差距将无限增长。在分析相时钟时，我们引入了针对“球放入箱子”过程的新型技术和界限，这可能具有独立的研究价值。利用相时钟，我们获得了一种能够容忍最多f个故障的多数选择群体协议，该协议在O(log² n)并行时间内决定多数值，且每个节点使用多项式对数状态。

Keyword:

phase clock

Byzantine nodes

population protocols

balls into bins

Byzantine-Tolerant Phase Clock

摘要

期刊

机构

引用论文