Volume 10 (2014)
Article 16 pp. 421-451
How Many Bits Can a Flock of Birds Compute?
Received: August 3, 2012
Revised: October 30, 2014
Published: November 13, 2014
Revised: October 30, 2014
Published: November 13, 2014
Keywords: natural algorithms, dynamical systems, bird flocking, busy-beaver function
Categories: algorithms, lower bounds, natural algorithms, dynamical systems, flocking, busy-beaver function
ACM Classification: F.2.0
AMS Classification: 68W25
Abstract: [Plain Text Version]
We derive a tight bound on the time it takes for a flock of birds to reach equilibrium in a standard model. Birds navigate by constantly averaging their velocities with those of their neighbors within a fixed distance. It is known that the system converges after a number of steps no greater than a tower-of-twos of height logarithmic in the number of birds. We show that this astronomical bound is actually tight in the worst case. We do so by viewing the bird flock as a distributed computing device and deriving a sharp estimate on the growth of its busy-beaver function. The proof highlights the use of spectral techniques in natural algorithms.
Licensed under a Creative Commons Attribution License (CC-BY)