Distributed applications require coordination between multiple nodes in a network, and they need to continue to operate correctly despite node failures. Implementation of such applications benefits from the availability of distributed primitives for commonly used distributed operations, such as clock synchronization or consensus. While most of the past distributed applications have traditionally used wired networks, there is an emerging trend towards the use of wireless networks for distributed applications.
The focus of this interdisciplinary project is on design, analysis and implementation of distributed primitives for wireless networks. In wireless networks, the network capacity is often quite limited. This project explores the design of efficient algorithms for distributed primitives under network capacity constraints, while exploiting wireless network capabilities such as local broadcast and physical layer adaptation. The scope of the project includes network-constrained distributed primitives for synchronization, consensus and function computation. Expected results from the project include theoretical bounds on performance of distributed primitives under network capacity constraints, design of efficient algorithms for the primitives, and practical implementations based on insights gained from the theory. Outcomes from the project are expected to allow efficient implementation of future distributed applications in resource-constrained wireless networks. The project brings together networking and distributed systems viewpoints, and is expected to yield fundamental new insights of interest to both areas. The research outcomes from this project will be disseminated via publications in technical conferences and journals, and incorporated into distributed computing and wireless networking courses.
The goal of this project is to understand the impact of network characteristics and constraints on the performance of distributed algorithms, and design and analysis of suitable network-constrained algorithms. Of particular interest is the interaction between distributed computation and communication cost of the distributed algorithms, as well as the impact of link capacity constraints, and properties such as wireless broadcast and transmission losses, on algorithm design and performance. The project resulted in the development of several distributed algorithms, particularly for Byzantine consensus, Byzantine broadcast, and average consensus problems. The goal of Byzantine consensus and broadcast is to allow the nodes in a network to reach agreement on a valid output despite the presence of faulty nodes that may behave arbitrarily. The average consensus algorithm can be used by the nodes to compute average of the inputs at the different nodes, while performing a fully distributed computation. The project resulted in the development of algorithms for Byzantine consensus and Byzantine broadcast that take into account link capacity constraints, and development of bounds on optimal performance under link capacity constraints. The project also yielded a complete characterization of networks of directed links that can solve the Byzantine consensus problem. Additionally, several iterative Byzantine consensus algorithms were developed, which require communication only between adjacent nodes, and yet achieve Byzantine consensus. These iterative algorithms achieve scalar consensus, vector consensus, and convex consensus. We also developed communication-efficient algorithms for Byzantine broadcast and consensus that attempt to achieve low total communication cost over all network links combined. The algorithms make judicious use of error detection codes to improve efficiency. The project investigated the design of a Byzantine broadcast algorithm over a wireless channel. It also addressed the design of an average consensus algorithm over a lossy wireless broadcast channel, and showed that average consensus can be achieved using a simple iterative algorithm, which only requires each node to have the knowledge of its local topology. A software tool was also developed to simulate and visualize the state of the average consensus algorithm. The project has enhanced the understanding of the impact of communication network characteristics on the performance of distributed computations. The algorithms developed in this project have potential applications in a broad range of cyber-physical systems, particularly when tolerance of compromised or faulty nodes is required. The project provided an opportunity for graduate and undergraduate students to participate in a research activity of significant potential impact. The project outcomes were used in presentations aimed at educating the research community about the significant interactions between communication costs and distributed computations.
