How many bits can a flock of birds compute?

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)421-451
Number of pages31
JournalTheory of Computing
Volume10
DOIs
StatePublished - Nov 13 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Bird flocking
  • Busy-beaver function
  • Dynamical systems
  • Natural algorithms

Fingerprint

Dive into the research topics of 'How many bits can a flock of birds compute?'. Together they form a unique fingerprint.

Cite this