Desynchronization: The theory of self-organizing algorithms for round-robin scheduling

Ankit Patel, Julius Degesys, Radhika Nagpal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

49 Scopus citations

Abstract

The study of synchronization has received much attention in a variety of applications, ranging from coordinating sensors in wireless networks to models of fireflies flashing in unison in biology. The inverse problem of desynchronization, however, 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 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 desynchronization: DESYNC and INVERSE-MS. Both algorithms are simple and decentralized and are able to self-adjust to the addition and removal of agents. Furthermore, neither requires a global clock or explicit fault detection. We prove convergence, compute bounds for the running time, and assess the various tradeoffs. To our knowledge, the theory of self-organizing desynchronization algorithms is presented here for the first time.

Original languageEnglish (US)
Title of host publicationFirst International Conference on Self-Adaptive and Self-Organizing Systems, SASO 2007
Pages87-96
Number of pages10
DOIs
StatePublished - 2007
Externally publishedYes
EventFirst International Conference on Self-Adaptive and Self-Organizing Systems, SASO 2007 - Cambridge, MA, United States
Duration: Jul 9 2007Jul 11 2007

Publication series

NameFirst International Conference on Self-Adaptive and Self-Organizing Systems, SASO 2007

Conference

ConferenceFirst International Conference on Self-Adaptive and Self-Organizing Systems, SASO 2007
Country/TerritoryUnited States
CityCambridge, MA
Period7/9/077/11/07

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Desynchronization: The theory of self-organizing algorithms for round-robin scheduling'. Together they form a unique fingerprint.

Cite this