דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

ceClub: Improved Bounds for Byzantine Self-Stabilizing Clock Synchronization
event speaker icon
כריסטוף לנזן (מכון ויצמן למדע)
event date icon
יום רביעי, 13.6.2012, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
The challenging task of Byzantine self-stabilizing pulse synchronization requires that, in the presence of a minority of nodes that are permanently maliciously faulty, the non-faulty nodes must start firing synchronized pulses in a regular fashion after a finite amount of time, regardless of the initial state of the system. We study this problem under full connectivity in a model where nodes have local clocks of unknown, but bounded drift, and messages are delayed for an unknown, but bounded time.

We present a generic scheme that, given a synchronous consensus protocol P, defines a self-stabilizing pulse synchronization algorithm A(P). If P terminates within R rounds (deterministically or with high probability), A(P) stabilizes within O(R) time (deterministically or with high probability, respectively). Utilizing different consensus routines, our transformation yields various improvements over previous techniques in terms of stabilization time and bit complexity. Finally, we sketch how to establish the abstraction of synchronous, integer-labeled rounds on top of pulse synchronization, at essentially the same complexity bounds.

We will discuss our approach and its merits assuming no previous knowledge on the problem, however, basic familiarity with consensus will be beneficial.
[בחזרה לאינדקס האירועים]