Optimal Clock Synchronization with Signatures

DOI10.1145/3519270.3538444arXiv2203.02553MaRDI QIDQ6202201FDOQ6202201

Christoph Lenzen, Julian Loss

Publication date: 26 March 2024

Published in: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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., maximum phase offset) despite local clock rates varying between $1$ and $vartheta>1$, end-to-end communication delays varying between $d-u$ and $d$, and the interference from malicious parties. So far, it is only known that clock pulses of skew $d$ can be generated with (trivially optimal) resilience of $lceiln/2ceil-1$ (PODC `19), improving over the tight bound of $lceiln/3ceil-1$ holding without signatures for emph{any} skew bound (STOC `84, PODC `85). Since typically $dggu$ and $vartheta-1ll1$, this is far from the lower bound of $u+(vartheta-1)d$ that applies even in the fault-free case (IPL `01). We prove matching upper and lower bounds of $Theta(u+(vartheta-1)d)$ on the skew for the resilience range from $lceiln/3ceil$ to $lceiln/2ceil-1$. The algorithm showing the upper bound is, under the assumption that the adversary cannot forge signatures, deterministic. The lower bound holds even if clocks are initially perfectly synchronized, message delays between honest nodes are known, $vartheta$ is arbitrarily close to one, and the synchronization algorithm is randomized. This has crucial implications for network designers that seek to leverage signatures for providing more robust time. In contrast to the setting without signatures, they must ensure that an attacker cannot easily bypass the lower bound on the delay on links with a faulty endpoint.

Full work available at URL: https://arxiv.org/abs/2203.02553

zbMATH Keywords

digital signaturesfault toleranceclock synchronization

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

This page was built for publication: Optimal Clock Synchronization with Signatures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202201)