ITR/SY: Communication and Data Sharing Services for Dynamic Distributed Systems

该项目正在开发和分析算法，以解决高度动态的分布式环境中的通信和数据共享问题，例如移动和嵌入式设备网络中的通信和数据共享。这里的术语动态包括多种类型的更改，包括更改网络拓扑、处理器移动性、更改参与的客户端进程集、各种类型的处理器和网络故障以及时序变化。正在研究的特性包括通信的有序性和可靠性保证以及数据共享的一致性保证。算法的结果伴随着下限和不可能的结果，这些结果描述了什么问题可以解决以及以什么代价解决的内在限制。这在需要受诸如有限的电池功率、存储容量、通信带宽和计算能力等资源限制的嵌入式设备的网络中尤其重要。需要解决的通信和数据共享问题被视为跨越网络位置的高水平全球服务。这些服务通常提供性能和容错保证，条件是对环境和底层网络底层的行为做出假设。传统上，对分布式服务的研究强调规范和正确性，而对分布式算法的研究则强调复杂性和性能。这个项目结合并综合了这两个问题：它产生了在动态分布式系统中高效执行和优雅降级的算法，其正确性、性能和容错保证由精确定义的全局服务表示。由于设置如此复杂，算法也非常复杂，这意味着有必要将它们分解成更小、更易于管理的片段。在这个项目中，其中许多较小的部分被视为较低级别的辅助全球服务。这些辅助服务提供较低级别的通信和数据共享功能，以及其他功能，如故障检测、进度检测、共识、组成员资格、领导人选举、重新配置、资源分配、工作负载分配、位置确定和路由。这项工作是在基于交互状态机的数学框架下进行的。状态机包括表示时间、连续行为和概率行为问题的功能。本项目的理论工作以移动和嵌入式设备网络系统的需求为指导，并从分布式文件管理、信息收集和传播、计算机支持的协作工作、分布式游戏和多媒体传输等几个原型应用中选择实例。

This project is developing and analyzing algorithms to solve problems of communication and data sharing in highly dynamic distributed environments such as found in networks of mobile and embedded devices. The term dynamic here encompasses many types of changes, including changing network topology, processor mobility, changing sets of participating client processes, a wide range of types of processor and network failures, and timing variations. The properties being studied include ordering and reliability guarantees for communication and coherence guarantees for data sharing. The algorithmic results are accompanied by lower bound and impossibility results, which describe inherent limitations on what problems can be solved, and at what cost. This is particulary important in the networks of embedded devices that need to operate subject to the resource constraints such limited battery power, storage capacity, communication bandwidth and computation power. The communication and data-sharing problems to be solved are viewed as high level global services, which span network locations. These services generally provide performance and fault-tolerance guarantees, conditioned on assumptions about the behavior of the environment and of the underlying network substrate. Traditionally, research on distributed services has emphasized specification and correctness, while research on distributed algorithms has emphasized complexity and performance. This project combines and synthesizes these two concerns: It yields algorithms that perform efficiently and degrade gracefully in dynamic distributed systems, and whose correctness, performance, and fault-tolerance guarantees are expressed by precisely-defined global services. Because the setting is so complex, the algorithms are also be very complex, which means that it it is necessary to decompose them into smaller, more manageable pieces. In this project, many of those smaller pieces are being viewed as lower-level, auxiliary global services. These auxiliary services provide lower-level communication and data-sharing capabilities, plus other capabilities such as failure detection, progress detection, consensus, group membership, leader election, reconfiguration, resource allocation, workload distribution, location determination, and routing. This work is being carried out in terms of a mathematical framework based on interacting state machines. The state machines include features to express issues of timing, continuous behavior, and probabilistic behavior. The theoretical work in this project is guided by the requirements of systems that include networks of mobile and embedded devices and examples chosen from several prototype applications, including distributed file management, information collection and dissemination, computer-supported cooperative work, distributed games, and multimedia transmission.