Making Network Protocols Simpler and More Robust Using Self-Stabilization

小行星94054444 随着网络成为国家基础设施的一部分，重要的是它们要像电话和电力服务等其他公用事业一样可靠。 这个项目关注的是通过使用自稳定来设计、评估和实现可靠的网络协议。 一个协议是自稳定的，如果它开始正确的行为，无论它开始在什么状态。 主要研究者认为，自稳定网络协议更简单（即，少量的统一机制而不是多个机制来处理预期故障的目录）和更鲁棒的（例如，可以从诸如存储器损坏的瞬时故障以及诸如链路和节点崩溃的常见故障中恢复）。 虽然在现有网络中存在自稳定协议，但此类协议通常依赖于与最坏情况的网络延迟成比例的定时器，并导致缓慢的恢复时间。此外，只有少数这样的协议。 这个项目将研究具有更快恢复时间和更大类问题的稳定协议。 这个项目将应用分布式算法理论（主要研究者和其他人已经开发的）的技术来系统地设计自稳定协议。 分布式算法文献中的工作已经引入了一些有用的范例和技术，但还没有完全将这些想法应用到真实的网络中。 这就是这个项目要解决的问题。 ***

94054444 Varghesee As networks become part of the nation's infrastructure, it is important that they become as reliable as other utilities such as the telephone and power services. This project is concerned with the design, evaluation, and implementation of reliable network protocols through the use of self-stabilization. A protocol is self-stabilizing if it begins to behave correctly no matter what state it starts in. The principal investigator believes that self-stabilizing network protocols are simpler (i.e., a small number of uniform mechanisms instead of multiple mechanisms to deal with a catalog of anticipated faults) and more robust (e.g., can recover from transient faults such as memory corruption as well as common faults such as link and node crashes). While there are self-stabilizing protocols in existing networks, such protocols typically rely on timers that are proportional to worst-case network delays and result in slow recovery times. Further, there are only a handful of such protocols. This project will investigate stabilizing protocols that have much faster recovery times and for a larger class of problems. This project will apply techniques from the theory of distributed algorithms (that the principal investigator and others have developed) to the systematic design of self-stabilizing protocols. The work in the distributed algorithm literature has introduced some useful paradigms and techniques but has not fully applied these ideas to real networks. It is this gap that this project will address. ***