Theory of Computing
-------------------
Title     : How Many Bits Can a Flock of Birds Compute?
Authors   : Bernard Chazelle
Volume    : 10
Number    : 16
Pages     : 421-451
URL       : https://theoryofcomputing.org/articles/v010a016

Abstract
--------

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.