Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks

麻省理工学院CSAIL南希·林奇这个项目正在发展理论基础-形式模型、复杂性度量、抽象问题定义、算法和不可能结果-以解释在现实的、不可靠的移动自组织网络(MANET)中哪些可以可靠地计算，哪些不能可靠地计算。这项工作的长期目标是为此类网络构建高质量、可靠、高性能的应用程序提供指导。激励应用包括数据管理、通信和协调(例如，人、机器人或车辆)。假设的MANET模型由一组移动节点组成，按照指定的约束移动。一个特殊的“真实世界”组件向移动节点提供关于当前时间和它们自己的位置的大致信息。节点使用本地无线广播进行通信，受现实消息传递的限制。“争用管理器”组件封装了指数退避等策略，告知节点何时可能成功传输。“冲突检测器”组件向每个节点提供(可能不可靠的)关于它可能没有接收到的消息的信息。其他人描述了旨在简化编写应用程序的任务的抽象，例如领导者和集群管理服务、组成员资格服务、位置服务和虚拟网络。对可靠性的需求源于应用的可靠性要求和对具有明确保证的抽象的需要。所寻求的结果是：(1)现实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.