Algorithms for Data Sharing, Coordination, and Communication in Dynamic Network Settings

摘要

This project developed many distributed algorithms and corresponding lower bounds for solving important problems in dynamic networks, focusing on mobile networks with wireless communication. Problems studied include data management, time synchronization, communication problems (broadcast, geocast, and point-to-point routing), distributed consensus, tracking, and motion coordination. Highlights include (1) The discovery of a fundamental limitation in capabilities for time synchronization in large networks. (2) The identification and development of the notion of 'Virtual Node Layers' as abstraction layers for programming mobile networks; these appear to facilitate programming of key communication services, as well as motion coordination for robots, vehicles and aircraft. (3) Upper and lower bounds for solving basic problems such as distributed consensus in mobile networks in which messages are subject to loss and collisions. (4) The development of a mathematical framework -- a combination of Timed and Probabilistic I/O Automata -- capable of modeling the dynamic networks and algorithms that were studied, and of supporting theorems about correctness and performance of the algorithms.