2010 | OriginalPaper | Buchkapitel
A Fault-Resistant Asynchronous Clock Function
verfasst von : Ezra N. Hoch, Michael Ben-Or, Danny Dolev
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Consider an asynchronous network in a shared-memory environment consisting of
n
nodes. Assume that up to
f
of the nodes might be
Byzantin
(
n
> 12
f
), where the adversary is full-information and dynamic (sometimes called adaptive). In addition, the non-
Byzantin
nodes may undergo transient failures. Nodes advance in atomic steps, which consist of reading all registers, performing some calculation and writing to all registers.
The three main contributions of the paper are: first, the clock-function problem is defined, which is a generalization of the clock synchronization problem. This generalization encapsulates previous clock synchronization problem definitions while extending them to the current paper’s model. Second, a randomized asynchronous self-stabilizing
Byzantin
tolerant clock synchronization algorithm is presented.
In the construction of the clock synchronization algorithm, a building block that ensures different nodes advance at similar rates is developed. This feature is the third contribution of the paper. It is self-stabilizing and
Byzantin
tolerant and can be used as a building block for different algorithms that operate in an asynchronous self-stabilizing
Byzantin
model.
The convergence time of the presented algorithm is exponential. Observe that in the asynchronous setting the best known full-information dynamic
Byzantin
agreement also has an expected exponential convergence time.