Theory of Self-Stabilizing Overlay Networks

Arizona State University, Scottsdale AZ

Investigators

Abstract

The rapid rise of overlay networks -- as for example, in the form of social networks and other peer-to-peer systems, sensor networks, or mobile ad hoc networks -- is revolutionizing the way we group and exchange information. However, not much is known about self-stabilization mechanisms for these highly dynamic networks. Minimum requirements for overlay network protocols to be useful in practice are that they be local, simple, and self-stabilizing. Locality is important for fast response times and for minimizing the impact of topology changes on the overlay network properties, simplicity is important so that the protocols can be used in a wide range of systems and for a formal verification of their effectiveness, and self-stabilization is important for automatic recovery from any illegal state since protocols requiring human intervention will not scale to systems potentially spanning millions of sites. This project provides mechanisms that allow overlay networks to self-stabilize from an arbitrary connected state in an efficient and robust way. Moreover, our mechanisms will self-stabilize from an arbitrary state even under adversarial behavior of some of the nodes. Since overlay networks and self-stabilization are used in many contexts, this project benefits a number of research communities within and outside of computer science. Moreover, it consolidates strong international collaboration with the Tech. U. of Munich, Germany, while advancing education and enhancing diversity at Arizona State University. This award is co-funded in part by NSF's Office of International Science and Engineering (OISE).