Nitin Vaidya
University of Illinois, Urbana-Champaign
Time: Friday, February 17th, 2012, 2:30 pm
Location: CEWIT 200

Network-Aware Distributed Algorithms

Abstract: In the past three decades, a large variety of distributed computing problems have been explored, and fundamental limits and optimal algorithms have been identified for many of these problems. Examples include clock synchronization, resource sharing, consensus or agreement, and naming. The distributed algorithms are typically executed by entities that are interconnected by a communication network. While some of the past work has taken into account the topology of the communication network, the impact of network capacity constraints on distributed algorithms has been largely ignored. In this talk, we discuss how the network capacity may affect distributed algorithms, with distributed agreement as the illustrative example. The distributed agreement (or consensus) problem arises in many contexts in distributed computing. Agreement in the presence of Byzantine faults is of interest when some of the nodes in the distributed system may fail or be compromised. In this talk, we will introduce efficient agreement algorithms that take the network capacity into account. The talk will conclude by discussing research challenges in the area of network-aware distributed algorithms.