Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus

Authors Christoph Lenzen, Joel Rybicki



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.32.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Christoph Lenzen
Joel Rybicki

Cite AsGet BibTex

Christoph Lenzen and Joel Rybicki. Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.32

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(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 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 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 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.
Keywords
  • Byzantine faults
  • self-stabilisation
  • clock synchronisation
  • consensus

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. M. K. Aguilera and S. Toueg. Simple bivalency proof that t-resilient consensus requires t+1 rounds. Information Processing Letters, 71(3):155-158, 1999. Google Scholar
  2. M. Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In PODC 1983, pages 27-30, 1983. Google Scholar
  3. M. Ben-Or, D. Dolev, and E. N. Hoch. Fast self-stabilizing Byzantine tolerant digital clock synchronization. In PODC 2008, pages 385-394, 2008. Google Scholar
  4. P. Berman, J. A. Garay, and K. J. Perry. Towards optimal distributed consensus. In FOCS 1989, pages 410-415, 1989. Google Scholar
  5. P. Berman, J. A. Garay, and K. J. Perry. Bit optimal distributed consensus. In Computer Science: Research and Applications, pages 313-321, 1992. Google Scholar
  6. A. Daliot, D. Dolev, and H. Parnas. Self-stabilizing pulse synchronization inspired by biological pacemaker networks. In SSS 2003, pages 32-48, 2003. Google Scholar
  7. Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643-644, 1974. Google Scholar
  8. D. Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1):14-30, 1982. Google Scholar
  9. D. Dolev, M. Függer, C. Lenzen, and U. Schmid. Fault-tolerant algorithms for tick-generation in asynchronous logic. Journal of the ACM, 61(5):30:1-30:74, 2014. Google Scholar
  10. D. Dolev, J. Y. Halpern, and H. R. Strong. On the possibility and impossibility of achieving clock synchronization. Journal of Computer and System Sciences, 32(2):230-250, 1986. Google Scholar
  11. D. Dolev, K. Heljanko, M. Järvisalo, J. H. Korhonen, C. Lenzen, J. Rybicki, J. Suomela, and S. Wieringa. Synchronous counting and computational algorithm design. Journal of Computer and System Sciences, 82(2):310-332, 2016. Google Scholar
  12. D. Dolev and E. N Hoch. Byzantine self-stabilizing pulse in a bounded-delay model. In SSS 2007, pages 234-252, 2007. Google Scholar
  13. D. Dolev, N. A. Lynch, S. S. Pinter, E. W. Stark, and W. E. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):499-516, 1986. Google Scholar
  14. D. Dolev and R. Reischuk. Bounds on information exchange for Byzantine agreement. Journal of the ACM, 32(1):191-204, 1985. Google Scholar
  15. S. Dolev. Self-Stabilization. Cambridge, MA, 2000. Google Scholar
  16. S. Dolev and J. L. Welch. Self-stabilizing clock synchronization in the presence of Byzantine faults. Journal of the ACM, 51(5):780-799, 2004. Google Scholar
  17. A. D. Fekete. Asymptotically optimal algorithms for approximate agreement. Distributed Computing, 4(1):9-29, 1990. Google Scholar
  18. P. Feldman and S. Micali. Optimal algorithms for Byzantine agreement. In STOC 1988, pages 148-161, 1988. Google Scholar
  19. M. J. Fischer and N. A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183-186, 1982. Google Scholar
  20. P. Khanchandani and C. Lenzen. Self-stabilizing Byzantine clock synchronization with optimal precision. In SSS 2016, pages 213-230, 2016. Google Scholar
  21. V. King and J. Saia. Breaking the O(n²) bit barrier. Journal of the ACM, 58(4):1-24, 2011. Google Scholar
  22. L. Lamport and P. M. Melliar-Smith. Synchronizing clocks in the presence of faults. Journal of the ACM, 32(I):52-78, 1985. Google Scholar
  23. L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982. Google Scholar
  24. C. Lenzen, M. Függer, M. Hofstätter, and U. Schmid. Efficient construction of global time in SoCs despite arbitrary faults. In DSD 2013, pages 142-151, 2013. Google Scholar
  25. C. Lenzen and J. Rybicki. Efficient counting with optimal resilience. In DISC 2015, pages 16-30, 2015. Google Scholar
  26. C. Lenzen and J. Rybicki. Near-optimal self-stabilising counting and firing squads. In SSS 2016, pages 263-280, 2016. Google Scholar
  27. C. Lenzen and J. Rybicki. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus, 2017. Full version. URL: http://arxiv.org/abs/1705.06173.
  28. C. Lenzen, J. Rybicki, and J. Suomela. Towards optimal synchronous counting. In PODC 2015, pages 441-450, 2015. Google Scholar
  29. J. Lundelius and N. Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2-3):190-204, 1984. Google Scholar
  30. M. C. Pease, R. E. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980. Google Scholar
  31. M. O. Rabin. Randomized Byzantine generals. In FOCS 1983, pages 403-409, 1983. Google Scholar
  32. M. Raynal. Fault-tolerant agreement in synchronous message-passing systems. Morgan &Claypool, 2010. Google Scholar
  33. T. K. Srikanth and S. Toueg. Optimal clock synchronization. Journal of the ACM, 34(3):626-645, 1987. Google Scholar
  34. J. L. Welch and N. Lynch. A new fault tolerant algorithm for clock synchronization. Information and Computation, 77(1):1-36, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail