To refer to this page use:
|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.|
|Citation:||Chazelle, Bernard. "How Many Bits Can a Flock of Birds Compute?" Theory of Computing 10, no. 16 (2014): pp. 421-451. doi:10.4086/toc.2014.v010a016|
|Pages:||421 - 451|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||Theory of Computing|
|Version:||Final published version. This is an open access article.|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.