Optimal Clock Synchronization with Signatures
Optimal Clock Synchronization with Signatures
复制标题
带有签名的最佳时钟同步
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
J. Loss
中科院分区：
文献类型：
--
作者：
C. Lenzen;J. Loss
加密签名可以通过增加可以容忍的错误方的数量来增加分布式系统对对抗性攻击的弹性。虽然这是很好的研究共识，它一直在容错时钟同步的上下文中，即使在完全连接的系统中探索不足。这里，n节点系统的诚实方需要计算小偏斜的输出时钟（即，相位偏移），而不管本地时钟速率在1和ω> 1之间变化、端到端通信延迟在d-u和d-u之间变化以及来自恶意方的干扰。具有[n/2] - 1的（平凡最优）弹性的已知算法在没有签名的情况下保持[n/3] - 1的紧界上改进了任何偏斜界[6，18]，但会导致偏斜d [1]或Ω（n（u +（n- 1）d））[14]。由于通常d >> u且n- 1 <<1，这与即使在无故障情况下也适用的u +（n- 1）d的下限相差甚远[3]。
Cryptographic signatures can be used to increase the resilience of distributed systems against adversarial attacks, by increasing the number of faulty parties that can be tolerated. While this is well-studied for consensus, it has been underexplored in the context of fault-tolerant clock synchronization, even in fully connected systems. Here, the honest parties of an n-node system are required to compute output clocks of small skew (i.e., phase offset) despite local clock rates varying between 1 and ϑ > 1, end-to-end communication delays varying between d - u and d, and the interference from malicious parties. Known algorithms with (trivially optimal) resilience of [n/2] - 1 improve over the tight bound of [n/3] - 1 holding without signatures for any skew bound [6, 18], but incur skew d [1] or Ω(n(u + (ϑ - 1)d)) [14]. Since typically d >> u and ϑ - 1 « 1, this is far from the lower bound of u + (ϑ - 1)d that applies even in the fault-free case [3].