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).
We are living in the information age. The ability to exchange information quickly and reliably is a vital part of our everyday life. Therefore, it is of utmost importance to provide a communication infrastructure that is highly available and robust. Due to the rapid rise of social networks and other peer-to-peer systems, sensor networks, and mobile ad-hoc wireless networks, overlay networks are becoming more and more wide spread. A major complication in these networks is that they are usually dynamic in nature. The topology and the link rates may frequently change, which requires highly efficient update mechanisms to preserve desirable network properties. 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 canbe 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. We focus here on overlay networks for the Internet though we expect our results to be also useful for sensor networks and ad hoc networks since our protocols are local and simple. 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. This project consolidates the strong international collaboration with the University of Paderborn, Germany, while advancing education and enhancing diversity at Arizona State University.
