- Series
- ACO Student Seminar
- Time
- Friday, September 16, 2016 - 1:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Sarah Cannon – Georgia Tech – sarah.cannon@gatech.edu – http://www.cc.gatech.edu/grads/s/scannon7/
- Organizer
- Marcel Celaya
I will present work on a new application of Markov chains to distributed
computing. Motivated by programmable matter and the behavior of
biological distributed systems such as ant colonies, the geometric
amoebot model abstracts these processes as self-organizing particle
systems where particles with limited computational power move on the
triangular lattice. Previous algorithms developed in this setting have
relied heavily on leader election, tree structures that are not robust
to failures, and persistent memory. We developed a distributed algorithm
for the compression problem, where all particles want to gather
together as tightly as possible, that is based on a Markov chain and is
simple, robust, and oblivious. Tools from Markov chain analysis enable
rigorous proofs about its behavior, and we show compression will occur
with high probability. This joint work with Joshua J. Daymude, Dana
Randall, and Andrea Richa appeared at PODC 2016. I will also present
some more recent extensions of this approach to other problems, which is
joint work with Marta Andres Arroyo as well.