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).