Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks

Nancy Lynch，MIT CSAIL这个项目正在开发理论基础-形式模型，复杂性度量，抽象问题定义，算法和不可能性结果-来解释在现实的，不可靠的移动的ad hoc网络（MANDO）中什么可以和什么不能可靠地计算。这项工作的长期目标是为此类网络构建高质量，可靠，高性能的应用程序提供指导。 激励应用程序包括数据管理、通信和协调（例如，假设的MANET模型由根据指定约束移动的移动的节点的集合组成。 特殊的"真实的世界“组件为移动的节点提供关于当前时间和它们自己的位置的近似信息。 节点使用本地无线电广播进行通信，受到现实的消息传递约束。 一个“竞争管理器”组件封装了指数退避等策略，告知节点何时能够成功传输。 一个“冲突检测器”组件提供（可能不可靠）的信息，每个节点的消息，它可能没有收到。 还有一些描述了旨在简化编写应用程序的任务的抽象，例如领导者和集群管理服务、组成员服务、位置服务和虚拟网络。 对可靠性的需求来自于应用的可靠性要求和对具有明确保证的抽象的需求。(2)具有强可靠性要求的应用和抽象问题的定义。(3)这些问题的有效算法和相应的不可能性结果。(4)集成各个算法的结果，以产生端到端的保证高层次的问题，在基本的MANET模型。

"Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks"Nancy Lynch, MIT CSAILThis project is developing theoretical foundations---formal models, complexity measures, abstract problem definitions, algorithms, and impossibility results---to explain what can and what cannot be computed reliably in realistic, unreliable mobile ad hoc networks (MANETs). The long-range goal of this work is to provide guidance for building high quality, reliable, high performance applications for such networks. Motivating applications include data management, communication, and coordination (e.g., of people, robots, or vehicles).The assumed MANET model consists of a collection of mobile nodes, moving according to specified constraints. A special ``real world'' component provides the mobile nodes with approximate information about the current time and their own locations. Nodes communicate using local wireless radio broadcast, subject to realistic message delivery constraints. A ``contention manager'' component encapsulates strategies such as exponential backoff, advising nodes about when they are likely to be able to transmit successfully. A ``collision detector'' component provides (possibly unreliable) information to each node about messages that it might not have received.Some problems being studied arise directly from MANET applications. Others describe abstractions that are intended to simplify the task of writing applications, such as leader and cluster management services, group membership services, location services, and virtual networks. The need for reliability arises from reliability requirements of the applications and from the need for abstractions with clear guarantees.Results being sought are:(1) Definitions of realistic MANET models.(2) Definitions of application and abstraction problems with strong reliability requirements.(3) Efficient algorithms and corresponding impossibility results for these problems.(4) Integration of individual algorithmic results to yield end-to-end guarantees for high-level problems in terms of the basic MANET model.