Making Network Protocols Simpler and More Robust Using Self-Stabilization

点击翻译按钮获取中文摘要

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