Linear-time Self-stabilizing Byzantine Clock Synchronization

Details Linear-time Self-stabilizing Byzantine Clock Synchronization Linear-time Self-stabilizing Byzantine Clock Synchronization

2006-08-25

arxiv.org/abs/cs/0608096v1

Proc. of 7th International Conference on Principles of Distributed Systems (OPODIS'03 La Martinique, France), December, 2003

Computer Science

Distributed, Parallel, and Cluster Computing

This is a corrected version. The original paper appeared in OPODIS'03

Scientific paper

Clock synchronization is a very fundamental task in distributed system. It thus makes sense to require an underlying clock synchronization mechanism to be highly fault-tolerant. A self-stabilizing algorithm seeks to attain synchronization once lost; a Byzantine algorithm assumes synchronization is never lost and focuses on containing the influence of the permanent presence of faulty nodes. There are efficient self-stabilizing solutions for clock synchronization as well as efficient solutions that are resilient to Byzantine faults. In contrast, to the best of our knowledge there is no practical solution that is self-stabilizing while tolerating the permanent presence of Byzantine nodes. We present the first linear-time self-stabilizing Byzantine clock synchronization algorithm. Our deterministic clock synchronization algorithm is based on the observation that all clock synchronization algorithms require events for exchanging clock values and re-synchronizing the clocks to within safe bounds. These events usually need to happen synchronously at the different nodes. In classic Byzantine algorithms this is fulfilled or aided by having the clocks initially close to each other and thus the actual clock values can be used for synchronizing the events. This implies that clock values cannot differ arbitrarily, which necessarily renders these solutions to be non-stabilizing. Our scheme suggests using an underlying distributed pulse synchronization module that is uncorrelated to the clock values.

Affiliated with

Also associated with

No associations

Rating

Linear-time Self-stabilizing Byzantine Clock 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 Linear-time Self-stabilizing Byzantine Clock Synchronization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear-time Self-stabilizing Byzantine Clock Synchronization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-111359