Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Leader Election in Rings with Bounded Multiplicity (Short Paper) Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Self-stabilizing Byzantine Clock Synchronization with Optimal Precision

verfasst von : Pankaj Khanchandani, Christoph Lenzen

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

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel An Efficient Silent Self-stabilizing 1-Maximal Matching Algorithm Under Distributed Daemon Without Global Identifiers
Nächstes Kapitel DecTDMA: A Decentralized-TDMA
Fußnoten
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.
 
Literatur
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.
Dolev, S., Welch, J.L.: Self-stabilizing clock synchronization in the presence of byzantine faults. J. ACM 51(5), 780–799 (2004)MathSciNetCrossRefMATH
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.
Metadaten
Titel
Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
verfasst von
Pankaj Khanchandani
Christoph Lenzen
Copyright-Jahr
2016
Buch
Stabilization, Safety, and Security of Distributed Systems

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

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

Copyright-Jahr: 2016

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

Premium Partner

    Bildnachweise