Report an accessibility problem

Self-Organizing Particle Systems

Collaborative Computation in Self-Organizing Particle Systems

Alexandra Porter and Andréa W. Richa.

[arXiv] [Online] — Conference paper in Unconventional Computation and Natural Computation – 17th International Conference (UCNC ’18), pp. 188-203, 2018.

Overview

The amoebot model constrains each particle to only a constant-size memory, meaning particles can’t store values that depend in any way on the size of the system. Even counting the number of particles in the system (say n) requires log(nbits. To overcome this obstacle, this paper addresses the fundamental primitive of organizing particles as distributed memory. In particular, we give algorithms for organizing particles as an increment-only binary counter and then use these counters to achieve matrix-vector multiplication. We prove that our algorithms count to a value v in O(vasynchronous rounds and multiply an h w matrix by a w1 vector in O(wasynchronous rounds.

To demonstrate these primitives’ utility, we show how they can be used by self-organizing particle systems to implement image processing algorithms.

Resources

None.

Press

None.

BibTeX

@InProceedings{Porter2018,
  title     = {Collaborative Computation in Self-Organizing Particle Systems},
  author    = {Porter, Alexandra and Richa, Andréa W.},
  booktitle = {Unconventional Computation and Natural Computation},
  series    = {UCNC '18},
  pages     = {188--203},
  year      = {2018}
}

Related Publications

The increment-only distributed binary counters described in this work were later generalized to include decrement and zero-test operations in the Convex Hull paper (2019).