Skip to main content

How Many Bits Can a Flock of Birds Compute?

Author(s): Chazelle, Bernard

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.
Publication Date: 2014
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
DOI: 10.4086/toc.2014.v010a016
ISSN: 1557-2862
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.