Eric Ruppert, York University
(joint work with Rachid Guerraoui)
Thursday April 22nd, 2:30p.m. Salle Sicile (F302)
Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
This talk will briefly describe the population protocol model of ad hoc mobile computing in which agents have severely restricted memory, highly unpredictable movement and no initial knowledge of the system. Then, it will describe how the model changes when agents are given unique identitifiers. In the new model, each agent’s memory can store O(1) bits, the unique identifier, and O(1) other agents’ identifiers. Inputs are distributed across n agents, and all agents must converge to the correct output value. We give a universal construction that proves the model is surprisingly strong: It can solve any decision problem in NSPACE(n log n). Moreover, the construction is robust with respect to Byzantine failures of a constant number of agents.