Pulse-coupled Oscillators

Inspired by the flashing of fireflies, the contractions of cardiac cells, and the firing of neurons, the pulse-coupled oscillator framework is used to model networks of agents that fire periodically. Using only the firings from nearby agents, agents can change the timing of their own firings so as to produce phenomena such as synchronization.

The seminal work in this field belongs to Mirollo and Strogatz: in 1991, they were the first to provide a plausible algorithm that modeled the spontaneous synchronization of fireflies in Southeast Asia. Furthermore, they were able to prove that a whole class of algorithms would always result in a fully-connected system (a system in which each agent can hear/see every other agent) being synchronized. This result was later extended by Lucarelli and Wang in 2004, when it was shown that the algorithms developed by Mirollo and Strogatz would converge on any connected topology.

This development naturally led to the question of whether this algorithm can be used in practice to synchronize devices that are subject to delays in communication; for in many settings, devices may not be able to "fire" when they want to. Geoffrey Werner-Allen, Geetika Tewari, Ankit Patel, Matt Welsh, and Radhika Nagpal presented work in 2005 that showed that if the agents are provided with memory, then delays in the message propagation can be tolerated without inhibiting the quality of synchronization as long as it can be determined when the devices actually wanted to originally fire.

Julius Degesys, Prithwish Basu, and Jason Redi further modified this algorithm in 2008. By requiring devices to only fire probabilistically and by ignoring certain firings, the modified algorithm drives a system to synchronization using much less time and far fewer messages than previous algorithms.

Our group has also focused on what may be considered the opposite problem of synchronization--namely, desynchronization. Instead of bringing a system to a state in which the agents fire at the same time (in effect, a state with a common heartbeat), desynchronization algorithms drive the system to a state in which devices try to spread their firings apart--imagine fireflies flashing in a round-robin manner.

Desynchronization is useful in many instances in which many agents need to exclusively share a resource. By forming "slots" around each of the firings, the round-robin-style firing pattern enables a collision-free schedule for the agents. This can be used in ad-hoc settings for which there would be a significant overhead or difficulty in constructing a centralized mechanism. This work also appears to be related to graph coloring. These connections are currently being explored.

Publications

Julius Degesys and Radhika Nagpal. Towards Desynchronization of Multi-hop Topologies. In Proceedings of the Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO). Venice, Italy. October 2008. [PDF] [PS]

Julius Degesys, Prithwish Basu, and Jason Redi. Synchronization of Strongly Pulse-Coupled Oscillators with Refractory Periods and Random Medium Access. In Proceedings of the 23rd Annual ACM Symposium on Applied Computing (SAC). Fortaleza, Ceara, Brazil. March 2008. [PDF] [PS]

Ankit Patel, Julius Degesys, and Radhika Nagpal. Desynchronization: The Theory of Self-Organizing Algorithms for Round-Robin Scheduling. In Proceedings of the First IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO). Boston, MA. July 2007. [PDF] [PS]

Julius Degesys, Ian Rose, Ankit Patel, and Radhika Nagpal. DESYNC: Self-Organizing Desynchronization and TDMA on Wireless Networks. In Proceedings of the Sixth International Conference on Information Processing in Sensor Networks (IPSN). Cambridge, MA. April 2007. [PDF] [PS]

Conference Talks

IPSN - April 25, 2007 [PPT]

Videos

DESYNC Implementation Demo [MOV] (36MB)

Code

The TinyOS code is as-is, but please send an e-mail if you find bugs in the MATLAB code:
TinyOS: DESYNC
MATLAB: DESYNC/SYNC