loading...
Desynchronization: The Theory of Self-Organizing Algorithms for Round-Robin Scheduling
Cambridge, Massachussets July 09-July 11
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SASO.2007.17First International Conference on Sel ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Ankit Patel, Harvard University
Julius Degesys, Harvard University
Radhika Nagpal, Harvard University
The study of synchronization has received much attention in a variety of applications, ranging from coordinating sensors in wireless networks to models of firefies 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 analogto- digital converters, and achieving high-throughput traf- fic 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.
Citation:
Ankit Patel, Julius Degesys, Radhika Nagpal, "Desynchronization: The Theory of Self-Organizing Algorithms for Round-Robin Scheduling," saso, pp.87-96, First International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.