InterJournal Complex Systems, 77
Status: Accepted
Manuscript Number: [77]
Submission Date: 963011
Self organizing device networks
Author(s): Joshua Smith

Subject(s): CX.07

Category: Brief Article

Abstract:

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.

Retrieve Manuscript
Submit referee report/comment


Public Comments: