Resilient Distributed Consensus

Nitin Vaidya

University of Illinois at Urbana-Champaign

Abstract

Consensus algorithms allow a set of nodes to reach an agreement on a quantity of interest. For instance, a consensus algorithm may be used to allow a network of sensors to determine the average value of samples collected by the different sensors. Similarly, a consensus algorithm can also be used by the nodes to synchronize their clocks. Research on consensus algorithms has a long history, with contributions from different research communities, including distributed computing, control systems, and social science.

In this talk, we will discuss two resilient consensus algorithms that can perform correctly despite the following two types of adversities: (i) In wireless networks, transmissions are subject to transmission errors, resulting in packet losses. We will discuss how "average consensus" can be achieved over such lossy links, without explicitly making the links reliable, for instance, via retransmissions. (ii) In a distributed setting, some of the nodes in the network may fail or may be compromised. We will discuss a consensus algorithm that can tolerate "Byzantine" failures in partially connected networks.

Biography

Nitin Vaidya is a Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. His research interests span distributed algorithms, fault-tolerant computing, and wireless networks. Nitin has held visiting positions at Technicolor Paris Lab, TU-Berlin, IIT-Bombay, Microsoft Research-Redmond, and Sun Microsystems, as well as a faculty position at the Texas A&M University. He has co-authored papers that received awards at several conferences, including 2007 ACM MobiHoc and 1998 ACM MobiCom. He has served as the Editor-in-Chief for the IEEE Transactions on Mobile Computing. Nitin is a Fellow of the IEEE. For more information, please visit http://users.crhc.illinois.edu/nhv.