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

Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 66(5), 32.

Download
OA 2019_JACM_Lenzen.pdf 2.18 MB [Published Version]

Journal Article | Published | English

Scopus indexed
Author
Lenzen, Christoph; Rybicki, JoelISTA
Department
Abstract
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of thennodes 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 ofthe 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 nodesgenerate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner.Compared to prior work, we achieveexponentialimprovements in stabilisation time and the number ofcommunicated bits, and give the first sublinear-time algorithm for the problem:•In the deterministic setting, the state-of-the-art solutions stabilise in timeΘ(f)and have each nodebroadcastΘ(flogf)bits per time unit. We exponentially reduce the number of bits broadcasted pertime unit toΘ(logf)while retaining the same stabilisation time.•In the randomised setting, the state-of-the-art solutions stabilise in timeΘ(f)and have each nodebroadcastO(1)bits per time unit. We exponentially reduce the stabilisation time to polylogfwhileeach node broadcasts polylogfbits per time unit.These results are obtained by means of a recursive approach reducing the above task ofself-stabilisingpulse synchronisation in thebounded-delaymodel tonon-self-stabilisingbinary consensus in thesynchro-nousmodel. In general, our approach introduces at most logarithmic overheads in terms of stabilisation timeand broadcasted bits over the underlying consensus routine.
Publishing Year
Date Published
2019-09-01
Journal Title
Journal of the ACM
Publisher
ACM
Volume
66
Issue
5
Article Number
32
ISSN
IST-REx-ID

Cite this

Lenzen C, Rybicki J. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 2019;66(5). doi:10.1145/3339471
Lenzen, C., & Rybicki, J. (2019). Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. ACM. https://doi.org/10.1145/3339471
Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3339471.
C. Lenzen and J. Rybicki, “Self-stabilising Byzantine clock synchronisation is almost as easy as consensus,” Journal of the ACM, vol. 66, no. 5. ACM, 2019.
Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 66(5), 32.
Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” Journal of the ACM, vol. 66, no. 5, 32, ACM, 2019, doi:10.1145/3339471.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2019-10-25
MD5 Checksum
7e5d95c478e0e393f4927fcf7e48194e


Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 1705.06173

Search this title in

Google Scholar