Distributed Computing: Protocols are Everywhere!

Hammurabi Mendes
Ph.D. Candidate
Brown University
SERC 306
Monday, March 9, 2015 - 11:00
Computer systems increasingly operate in a concurrent and distributed fashion. Examples include networks of mobile devices and processors that integrate many computing cores. Human activities, such as deep-sea exploration, also rely on distributed sensors, or even mobile robots, running distributed algorithms. We call those algorithms protocols.
This talk focuses on a protocol solving a problem called "multidimensional $\epsilon$- approximate agreement". This abstract problem models a scenario where mobile entities (say, robots) must converge to nearby positions, even though some of these entities might behave arbitrarily, or even maliciously, by spreading confusion and uncertainty in the system. The protocol implements a fault-tolerant, distributed coordination scheme to overcome this abnormal behavior, promoting the convergence. Non-faulty entities never move outside their original operating area during the convergence, avoiding the risk of going through hazardous territory. In this talk, I will show how such a protocol is designed, and discuss the central role of protocol design in distributed computing, and its impact in general CS research.