Consensus and Agreement Protocols with Boundary Conditions:From leader-Follower Formations to Location-Free Geographic Routing in Adhoc Networks

Speaker: Dr. Ali Jadbabaie, University of Pennsylvania
Abstract: In this talk we provide a unified view of several distributed coordination and consensus algorithms which have appeared in various disciplines such as distributed systems, statistical physics, biology, computer graphics, robotics, and control theory over the past 2 decades. These algorithms have been proposed as a mechanism for demonstrating emergence of a global collective behavior (such as social aggregation in animals, schooling, flocking and synchronization) using purely local interactions. Utilizing tools from spectral graph theory and control and dynamical systems theory, we provide a rigorous analysis of these algorithms. Furthermore, we show that by imposing fixed boundary conditions (e.g., designating a leader) , one can obtain algorithms for a wide range of applications, from leader-follower swarms to synchronization in oscillator networks, and from shortest path routing to geographic routing without location information. Finally, we describe a one-parameter family of distributed consensus algorithms with boundary conditions, which at one extreme, recovers the well-known Bellman-Ford Algorithm for shortest-path routing, and at the other, results in a routing scheme based on diffusion, and mean-first passage times. Connections between these algorithms and harmonic functions, electric networks, and discrete Dirichlet problems are also discussed.
Biography: Peng Ning is currently an assistant professor of Computer Science in the College of Engineering at North Carolina State University. He received his PhD degree in Information Technology from George Mason University in 2001. Prior to his PhD study, he received an ME degree in Communication and Electronic Systems in 1997, and a BS degree in Information Science in 1994, both from University of Science and Technology of China. Peng Ning's research interests are mainly in computer and network security. His recent work is mostly in intrusion detection and security in ad-hoc and sensor networks. Peng Ning's research has been supported by the National Science Foundation (NSF), the Army Research Office (ARO), the Advanced Research and Development Activity (ARDA), and the NCSU/Duke Center for Advanced Computing and Communication (CACC). Peng Ning is a recipient of NSF CAREER award. He is on the editorial boards of Ad-Hoc & Sensor Networks: an International Journal and IEE Proceedings Information Security, and is a guest editor for Journal of Computer Security Special Issue on Security of Ad-Hoc and Sensor Networks. Peng Ning has served on organizing committees or program committees for over twenty technical conferences or workshops related to computer and network security. Peng Ning is a founding member of the NCSU Cyber Defense Laboratory. He is a member of the ACM, the ACM SIGSAC, the IEEE, and the IEEE Computer Society.
Presentation On: Friday,17 Februray, 2006,
11:00 a.m. in room 1115, CSIC