|
|
 |
|
NIA Seminar by Danny Dolev |
|
Date: September 15, 2005
Time: 10:00am
Location: NIA, Rm 137
Self-Stabilizing Byzantine Pulse Synchronization
Danny Dolev, The Hebrew University of Jerusalem
We present a distributed "pulse synchronization" algorithm, which targets at invoking regular and tightly synchronized pulses.
Designing algorithms that self-stabilize while at the same time tolerating an eventual fraction of permanent Byzantine failures present a special challenge due to the "ambition" of malicious nodes to hamper stabilization if the system tries to recover from a corrupted state. Pulse synchronization has been shown to be a powerful building block for designing algorithms in this severe fault model. The system may be in an arbitrary state in which the communication network may behave arbitrarily and in which there may be an unbounded number of concurrent Byzantine faulty nodes. The pulse synchronization algorithm will eventually converge once the communication network resumes delivering messages within bounded, some d, time units, and the fraction of permanent Byzantine nodes, f, obeys the n >= 3f+1 ratio, for a network of size n. The attained pulse synchronization tightness is 3d with a convergence time of O(f) communication rounds or three cycles.
A joint work with Ariel Daliot.
|
|
|
Home