Lecture Notes in Computer Science, 2003, Volume 2704/2003, 32-48, DOI: 10.1007/3-540-45032-7_3

Self-Stabilizing Pulse Synchronization Inspired by Biological Pacemaker Networks

Ariel Daliot, Danny Dolev and Hanna Parnas

View Related Documents

Abstract

We define the “Pulse Synchronization” problem that requires nodes to achieve tight synchronization of regular pulse events, in the settings of distributed computing systems. Pulse-coupled synchronization is a phenomenon displayed by a large variety of biological systems, typically overcoming a high level of noise. Inspired by such biological models, a robust and self-stabilizing pulse synchronization algorithm for distributed computer systems is presented. The algorithm attains near optimal synchronization tightness while tolerating up to a third of the nodes exhibiting Byzantine behavior concurrently. We propose that pulse synchronization algorithms can be suitable for a variety of distributed tasks that require tight synchronization but which can tolerate a bound variation in the regularity of the synchronized pulse invocations.
This research was supported in part by Intel COMM Grant — Internet Network/Transport Layer & QoS Environment (IXA).

Fulltext Preview

Image of the first page of the fulltext document