NeTS: Small: Impact of Wireless Network Characteristics on Distributed Computation

无线网络在许多领域都有当前和未来的应用，包括应急响应和救援、监测和监视、分布式传感、群机器人和智能电网。在这样的分布式系统中，无线网络对于允许系统中的不同代理进行通信并联合协调它们的活动是有用的。本项目研究设计有效的算法来实现分布式原语，同时考虑到通信网络的属性。感兴趣的协调原语包括共识，容错广播和分布式优化。例如，共识原语允许不同的代理同意共同的行动过程，作为不同代理建议的潜在不同行动的函数。这个项目的范围是在通信和计算的交叉点。该项目调查的无线网络特性，如易出错的链接，动态拓扑结构，广播媒体，和容量限制，对重要的分布式计算问题的算法的设计和性能的影响。两类算法是感兴趣的，即，迭代算法和无约束算法。迭代算法具有简单的迭代结构，并且它们维护少量的状态，并且仅需要关于底层网络拓扑的有限信息。无约束算法利用了更多的网络信息，可以获得更好的性能。因此，迭代算法和无约束算法实现复杂度和性能之间的不同权衡。该项目的目标包括拓扑控制，资源管理和动态适应分布式算法的性能的影响调查。该项目将提高对如何为实际无线网络设计鲁棒分布式算法的理解。该项目将涉及本科生和研究生。学生将获得宝贵的经验，在各种应用程序相关的分布式计算问题的工作。

Wireless networks have current and future applications in many domains, including emergency response and rescue, monitoring and surveillance, distributed sensing, swarm robotics, and smart grids. In such distributed systems, wireless networks are useful to allow the different agents in the system to communicate and jointly coordinate their activities. This project investigates design of efficient algorithms for implementing the distributed primitives while taking into account the properties of the communication network. Coordination primitives of interest include consensus, fault-tolerant broadcast, and distributed optimization. For instance, the consensus primitive allows the different agents to agree on a common course of action, as a function of potentially different actions suggested by different agents. The scope of this project is at the intersection of communication and computing. The project investigates the impact of wireless network characteristics such as error-prone links, dynamic topology, broadcast medium, and capacity constraints, on the design and performance of algorithms for important distributed computation problems. Two classes of algorithms are of interest, namely, iterative algorithms and unconstrained algorithms. Iterative algorithms have a simple iterative structure, and they maintain a small amount of state and require only limited information about the underlying network topology. Unconstrained algorithms utilize more information about the network, and can achieve better performance. Thus, iterative and unconstrained algorithms achieve different trade-offs between complexity and performance. The goals of the project include investigation of the impact of topology control, resource management, and dynamic adaptation on the performance of the distributed algorithms. The project will improve the understanding of how robust distributed algorithms can be designed for practical wireless networks. The project will involve undergraduate and graduate students. The students will gain valuable experience working on distributed computing problems that are relevant in a variety of applications.