October 7, 2009
Title: Gossip and Consensus: Reaching Agreement in Networks
Abstract: In many emerging network applications, it has become important for distributed agents to have a mechanism to agree upon some quantity. One example is the task of coordination of mobile agents, where agreement must be reached about current positions and future goals. In many networks, including sensor and vehicular ad-hoc networks, the communication range is limited and energy expenditure is a consideration. It becomes important to achieve the desired agreement using only local communication, i.e. exchanging data only with devices in a relatively small geographical neighbourhood. In this talk, I will provide an overview of the research that has focused on the development of distributed algorithms that strive to address this task. A key issue is how fast these algorithms converge to the solution, since this determines the amount of communication required. I will highlight the connections with spectral analysis of graphs and mixing times of Markov chains, and describe some of our recent research efforts to accelerate the convergence rate.
Biography: Mark Coates received the BE degree (first class honours) in computer systems engineering from the University of Adelaide, Australia, in 1995, and a PhD degree in information engineering from the University of Cambridge, UK, in 1999. He was awarded the Texas Instruments Postdoctoral Fellowship in 1999 and was a research associate and lecturer at Rice University, Texas, from 1999-2001. He joined the Department of Electrical and Computer Engineering of McGill University (Montreal, Quebec) in 2002, where he is currently an Associate Professor. His research interests include communication and sensor/actuator networks, statistical signal processing, and Bayesian and Monte Carlo inference.