|InterJournal Complex Systems, 77
|Manuscript Number: |
Submission Date: 963011
|Self organizing device networks|
Category: Brief Article
In order for simple, initially identical computational units to acquire unique identities, two ingredients are needed: a physical symmetry breaking mechanism and a distributed algorithm that makes use of this mechanism. After briefly considering non-thermodynamic sources of symmetry breaking, I settle on a reverse-biased diode as a source of symmetry breaking, and present three algorithms that make use of this source. I analyze the expected resource requirements (time, random bits, communication) of the algorithms, and note a trade off between these measures of algorithm complexity. I close by speculating about a framework for formalizing these trade-offs and determining the theoretical optimum performance of symmetry breaking protocols.
|Submit referee report/comment|