Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2006-08-24
Computer Science
Distributed, Parallel, and Cluster Computing
An updated version. The original version appeared as TR-2005-84, The Hebrew university, Aug. 2005
Scientific paper
The ``Pulse Synchronization'' problem can be loosely described as targeting to invoke a recurring distributed event as simultaneously as possible at the different nodes and with a frequency that is as regular as possible. This target becomes surprisingly subtle and difficult to achieve when facing both transient and permanent failures. In this paper we present an algorithm for pulse synchronization that self-stabilizes while at the same time tolerating a permanent presence of Byzantine faults. The Byzantine nodes might incessantly try to de-synchronize the correct nodes. Transient failures might throw the system into an arbitrary state in which correct nodes have no common notion what-so-ever, such as time or round numbers, and can thus not infer anything from their own local states upon the state of other correct nodes. The presented algorithm grants nodes the ability to infer that eventually all correct nodes will invoke their pulses within a very short time interval of each other and will do so regularly. Pulse synchronization has previously been shown to be a powerful tool for designing general self-stabilizing Byzantine algorithms and is hitherto the only method that provides for the general design of efficient practical protocols in the confluence of these two fault models. The difficulty, in general, to design any algorithm in this fault model may be indicated by the remarkably few algorithms resilient to both fault models. The few published self-stabilizing Byzantine algorithms are typically complicated and sometimes converge from an arbitrary initial state only after exponential or super exponential time.
Daliot Ariel
Dolev Danny
No associations
LandOfFree
Self-Stabilizing Byzantine Pulse Synchronization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Self-Stabilizing Byzantine Pulse Synchronization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-Stabilizing Byzantine Pulse Synchronization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-339100