Optimal Clock Synchronization with Signatures

Abstract

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].