The consensus problem refers to reaching agreement (on a certain quantity of interest, often the average) among all agents in a distributed system. This fundamental problem has many important applications such as distributed detection, estimation, and data fusion in sensor networks, coordination and cooperation of autonomous agents, and load balancing in distributed and parallel computing. Existing works on distributed consensus explore linear iterations based on reversible Markov chains. The convergence of such algorithms is bounded to be slow due to the diffusive behavior of the reversible chains. It has been observed that by overcoming the diffusive behavior, certain nonreversible chains lifted from reversible ones mix substantially faster than the original chains. In this talk, we discuss the idea of fast distributed consensus via lifting Markov chains, and propose a class of Location-Aided Distributed Averaging (LADA) algorithms for wireless networks, where nodes’ location information is used to construct nonreversible chains that facilitate distributed computing and cooperative processing. We first show that it is possible to achieve an -averaging time of in a wireless network with a transmission radius r with a centralized algorithm, which is close to a performance lower bound derived based on resistance, an invariant of Markov chains. We then present a distributed LADA algorithm, which utilizes only the direction information of neighbors to construct nonreversible chains. The constructed chain does not naturally possess a uniform stationary distribution, which is in turn compensated by a weight estimation procedure to yield the average estimate. It is shown that LADA achieves the same scaling law in averaging time as the centralized scheme in wireless networks for all r satisfying the connectivity requirement. Finally, we propose a cluster-based LADA (C-LADA) algorithm, which requires no central coordination for clustering, and provides the additional benefit of reduced message complexity compared with LADA.

Huaiyu Dai received the B.E. and M.S. degrees in electrical engineering from Tsinghua University, Beijing, China, in 1996 and 1998, respectively, and the Ph.D. degree in electrical engineering from Princeton University, Princeton, NJ in 2002. Currently he is an Assistant Professor of Electrical and Computer Engineering at NC State University. His research interests are in the general areas of communication systems and networks, advanced signal processing for digital communications, and communication theory and information theory. His current research focuses on distributed and collaborative information processing and crosslayer design (with a physical layer emphasis) in wireless ad hoc and sensor networks, distributed, multicell, multiuser MIMO communications, and associated information-theoretic and computation-theoretic analysis. He is an associate editor of IEEE Transactions on Wireless Communications, IEEE Signal P rocessing Magazine e-Newsletter, EURASIP Journal on Applied Signal Processing, and EURASIP Journal on Wireless Communications and Networking.