Lenzen, Christoph ;
Rybicki, Joel
SelfStabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Abstract
We give faulttolerant 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 selfstabilisation, 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 wellseparated 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 sublineartime algorithm for the problem:
 In the deterministic setting, the stateoftheart solutions stabilise in time Theta(f) and have each node broadcast Theta(f log f) bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to Theta(log f) while retaining the same stabilisation time.
 In the randomised setting, the stateoftheart solutions stabilise in time Theta(f) and have each node broadcast O(1) bits per time unit. We exponentially reduce the stabilisation time to polylog f while each node broadcasts polylog f bits per time unit.
These results are obtained by means of a recursive approach reducing the above task of selfstabilising pulse synchronisation in the boundeddelay model to nonselfstabilising 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.
BibTeX  Entry
@InProceedings{lenzen_et_al:LIPIcs:2017:7991,
author = {Christoph Lenzen and Joel Rybicki},
title = {{SelfStabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {32:132:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7991},
URN = {urn:nbn:de:0030drops79914},
doi = {10.4230/LIPIcs.DISC.2017.32},
annote = {Keywords: Byzantine faults, selfstabilisation, clock synchronisation, consensus}
}
12.10.2017
Keywords: 

Byzantine faults, selfstabilisation, clock synchronisation, consensus 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

12.10.2017 