Self-stabilising Byzantine clock synchronisation is almost as easy as consensus

DOI10.1145/3339471zbMATH Open1473.68025arXiv1705.06173OpenAlexW2969859287MaRDI QIDQ5215461FDOQ5215461

Authors: Christoph Lenzen, Joel Rybicki 

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the $n$ nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to $f<n/3$ ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem: - In the deterministic setting, the state-of-the-art solutions stabilise in time $Theta(f)$ and have each node broadcast $Theta(flogf)$ bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to $Theta(logf)$ while retaining the same stabilisation time. - In the randomised setting, the state-of-the-art solutions stabilise in time $Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We exponentially reduce the stabilisation time to $lo{g}^{O(1)}f$ while each node broadcasts $lo{g}^{O(1)}f$ bits per time unit. These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.

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

Recommendations

• Self-stabilising Byzantine clock synchronisation is almost as easy as consensus
• Principles of Distributed Systems
• Self-stabilizing Byzantine clock synchronization with optimal precision
• On Self-stabilizing Synchronous Actions Despite Byzantine Attacks
• Self-stabilizing clock synchronization in the presence of Byzantine faults

zbMATH Keywords

agreementByzantine faultstransient faultsclock drift

Mathematics Subject Classification ID

Randomized algorithms (68W20) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (7)

• Brief announcement: Self-stabilizing clock synchronization with 3-bit messages
• Self-stabilizing Byzantine clock synchronization with optimal precision
• Self-stabilizing Byzantine clock synchronization with optimal precision
• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• Title not available (Why is that?)
• Self-stabilising Byzantine clock synchronisation is almost as easy as consensus
• Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast

This page was built for publication: Self-stabilising Byzantine clock synchronisation is almost as easy as consensus

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