Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Leader Election in Rings with Bounded Multiplicity (Short Paper) Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Self-stabilizing Byzantine Clock Synchronization with Optimal Precision

Authors : Pankaj Khanchandani, Christoph Lenzen

Published in: Stabilization, Safety, and Security of Distributed Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We revisit the approach to Byzantine fault-tolerant clock synchronization based on approximate agreement introduced by Lynch and Welch. Our contribution is threefold: (i) We provide a slightly refined variant of the algorithm yielding improved bounds on the skew that can be achieved and the sustainable frequency offsets. (ii) We show how to extend the technique to also synchronize clock rates. This permits less frequent communication without significant loss of precision, provided that clock rates change sufficiently slowly. (iii) We present a coupling scheme that allows to make these algorithms self-stabilizing while preserving their high precision. The scheme utilizes a low-precision, but self-stabilizing algorithm for the purpose of recovery.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter An Efficient Silent Self-stabilizing 1-Maximal Matching Algorithm Under Distributed Daemon Without Global Identifiers
next chapter DecTDMA: A Decentralized-TDMA
Footnotes
1
For comparison, the critical value in [18] is smaller than 1.025, i.e., we can handle a factor 4 weaker bound on \(\vartheta -1\). Non-quartz oscillators used in space applications, where temperatures vary widely, may have \(\vartheta \) close to this value, cf. [1].
 
2
A prototype FPGA implementation achieves \(182\,\)ps skew [12], which is suitable for generating a system clock.
 
3
The framework in [15, 16] addresses frequency correction, but substantial specialization would be required to achieve good constants in the bounds.
 
4
d tends to be at least one or two orders of magnitude larger than U.
 
5
If a node has fewer than \(2f+1\) neighbors in a system tolerating f faults, it cannot distinguish whether it synchronizes to a group of f correct or f faulty neighbors.
 
6
Discretization can be handled by re-interpreting the discretization error as part of the delay uncertainty. All our algorithms use the hardware clock exclusively to measure bounded time differences.
 
7
Typically, e(r) is a monotone sequence, implying that simply \(E=\lim _{r\rightarrow \infty }e(r)\).
 
8
Dividing the measured local time differences by \((\vartheta +1)/2\) is an artifact of our “one-sided” definition of hardware clock rates from \([1,\vartheta ]\); in an implementation, one simply reads the hardware clocks (which exhibit symmetric error) without any scaling.
 
9
Given that hardware clock speeds may differ by at most factor \(\vartheta \), nodes need to be able to increase or decrease their rates by factor \(\vartheta \): a single deviating node may be considered faulty by the algorithm, so each node must be able to bridge this speed difference on its own.
 
Literature
1.
2.
Daliot, A., Dolev, D.: Self-Stabilizing Byzantine Pulse Synchronization. Computing Research Repository abs/cs/0608092 (2006)
3.
4.
Dolev, D., Függer, M., Lenzen, C., Posch, M., Schmid, U., Steininger, A.: Rigorously modeling self-stabilizing fault-tolerant circuits: an ultra-robust clocking scheme for systems-on-chip. J. Comput. Syst. Sci. 80(4), 860–900 (2014)MathSciNetCrossRefMATH
5.
Dolev, D., Függer, M., Lenzen, C., Schmid, U.: Fault-tolerant algorithms for tick-generation in asynchronous logic: robust pulse generation. J. ACM 61(5), 1–74 (2014)MathSciNetCrossRefMATH
6.
Dolev, D., Halpern, J.Y., Strong, H.R.: On the possibility and impossibility of achieving clock synchronization. J. Comput. Syst. Sci. 32(2), 230–250 (1986)MathSciNetCrossRefMATH
7.
Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33, 499–516 (1986)MathSciNetCrossRefMATH
8.
9.
FlexRay Consortium, et al.: FlexRay communications system-protocol specification. Version 2, 1 (2005)
10.
Függer, M., Armengaud, E., Steininger, A.: Safely stimulating the clock synchronization algorithm in time-triggered systems - a combined formal & experimental approach. IEEE Trans. Ind. Inf. 5(2), 132–146 (2009)CrossRef
11.
Függer, M., Schmid, U.: Reconciling fault-tolerant distributed computing and systems-on-chip. Distrib. Comput. 24(6), 323–355 (2012)CrossRefMATH
12.
Huemer, F., Kinali, A., Lenzen, C.: Fault-tolerant Clock Synchronization with High Precision. In: IEEE Symposium on VLSI (ISVLSI) (2016). to appear
13.
Kopetz, H., Bauer, G.: The time-triggered architecture. Proc. IEEE 91(1), 112–126 (2003)CrossRef
14.
15.
Schossmaier, K.: Interval-based Clock State and Rate Synchronization. Ph.D. thesis, Technical University of Vienna (1998)
16.
Schossmaier, K., Weiss, B.: An algorithm for fault-tolerant clock state and rate synchronization. In: 18th Symposium on Reliable Distributed Systems (SRDS), pp. 36–47 (1999)
17.
18.
Metadata
Title
Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
Authors
Pankaj Khanchandani
Christoph Lenzen
Copyright Year
2016
Book
Stabilization, Safety, and Security of Distributed Systems

Print ISBN: 978-3-319-49258-2

Electronic ISBN: 978-3-319-49259-9

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-49259-9_18

Premium Partner

    Image Credits