Pulse-coupled Oscillators

The Pulse-Coupled Oscillator (PCO) is a novel protocol inspired by models used in mathematical biology to justify the emergence of synchrony in the natural world. It is 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. 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. 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. Instead of bringing a system to a state in which the agents fire at the same time, 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.

Posted in: