Harvard Theory of Computation Seminar

The Theory of Desynchronization: Self-Organizing Algorithms for Periodic Resource Scheduling

Ankit Patel, Harvard.

Place and Time: Monday, February 12, Maxwell Dworkin 221 Refreshments at 2:30pm, talk at 2:45pm

ABSTRACT

Nature has inspired us with myriad examples of the phenomena of synchronization: Thousands of fireflies flashing in unison across the sky, women whose menstrual cycles spontaneously align, and heart cells beating in synchrony. The theory of self-organizing synchronization has a long and well-developed history, sparked by the seminal works of Peskin, Mirollo and Strogatz. Biologically-inspired algorithms for multi-agent synchronization have been simple, robust, and useful, especially in the coordination of sensors in a wireless sensor network.

But the inverse problem of desynchronization has received little notice. Desynchronization is a powerful primitive: given a set of identical oscillators, applying a desynchronization primitive spreads them throughout the period, resulting in a self-organized, round-robin schedule. This can be useful in several applications: medium access control in wireless sensor networks, designing fast analog-to-digital converters, and achieving high-throughput traffic intersections.

Here we present two biologically-inspired algorithms for achieving desynchrony among many agents: DESYNC and INVERSE-MS. Both algorithms are simple, decentralized and able to self-adjust to the addition and removal of agents. Furthermore, neither requires a global clock nor explicit fault detection. We prove convergence, compute bounds for the running time, and implement the DESYNC algorithm in an all-to-all sensor network, showing promising results.

To our knowledge, the theory and application of self-organizing desynchronization algorithms is novel.