A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock

A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local "pulse counter" that simulates the global clock in a synchronous network. In this paper, we present a time-optimal self-stabilizing sc...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on dependable and secure computing 2007-07, Vol.4 (3), p.180-190
Main Authors: Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Availability
Clocks
Clocks & watches
Communication
Computational modeling
Computer engineering
Computer networks
Computer science
Computer Systems Organization
COMPUTER-COMMUNICATION NETWORKS
Counting circuits
Digital Object Identifier
DISCRETE MATHEMATICS
Distributed algorithms
Distributed computing
Distributed networks
Graph Theory
Mathematical analysis
Mathematical models
Mathematics
Mathematics of Computing
Networks
Peer to peer computing
Pulse counters
Pulse generation
Reliability
Software engineering
Studies
Synchronization
Synchronizers
Synchronous
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local "pulse counter" that simulates the global clock in a synchronous network. In this paper, we present a time-optimal self-stabilizing scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each node can compute its pulse number as a function of its neighbors' pulse numbers. We also show that some of the popular correction functions for phase clock synchronization are not self-stabilizing in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter of the network, without invoking global operations. We argue that the use of unbounded counters can be justified by the availability of memory for counters that are large enough to be practically unbounded and by the existence of reset protocols that can be used to restart the counters in some rare cases where faults will make this necessary.
ISSN:1545-5971
1941-0018
DOI:10.1109/TDSC.2007.1007