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