Theory of Self-Stabilizing Overlay Networks

覆盖网络的迅速崛起--例如，以社交网络和其他对等系统、传感器网络或移动的自组织网络的形式--正在彻底改变我们分组和交换信息的方式。然而，对这些高度动态网络的自稳定机制知之甚少。覆盖网络协议在实践中有用的最低要求是它们是本地的、简单的和自稳定的。局部性对于快速响应时间和最小化拓扑变化对覆盖网络属性的影响是重要的，简单性是重要的，使得协议可以在广泛的系统中使用，并且对于其有效性的正式验证是重要的，并且自稳定对于从任何非法状态自动恢复是重要的，因为需要人为干预的协议不会扩展到可能跨越数百万个站点的系统。该项目提供了一种机制，允许覆盖网络以一种有效和鲁棒的方式从任意连接状态进行自稳定。此外，我们的机制将自稳定的任意状态，即使在敌对行为的一些节点。由于覆盖网络和自稳定在许多情况下使用，该项目有利于计算机科学内外的许多研究社区。此外，它还巩固了与技术的强大国际合作。联合该奖项由美国国家科学基金会国际科学与工程办公室（OISE）共同资助。

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).