A Distributed Algorithm for Gathering Many Fat Mobile Robots in the Plane

Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios Mavronicolas

Abstract: We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots only make local decisions. We use a state-machine representation to formulate the gathering problem and develop a distributed algorithm that solves the problem for any number of fat robots. The main idea behind the algorithm is to enforce the robots to reach a configuration in which all the following hold: (a) The robots’ centers form a convex hull in which all robots are on the convex, (b) Each robot can see all other robots, and (c) The configuration is connected: every robot touches another robot and all robots form together a connected formation.
We show that starting from any initial configuration, the fat robots eventually reach such a configuration and terminate yielding a solution to the gathering problem.

Guest: Chrysovalandis Agathangelou
Host: Shantanu Das

New Challenges and Algebraic Topology

Maurice Herlihy

Maurice Herlihy discusses his view on the challenges distributed computing faces in the future, describes some of his work on programming abstractions and how he uses algebraic topology as a tool to reason about distributed protocols.

Guest: Maurice Herlihy
Host: Zvi Lotker and Yvonne-Anne Pignolet