# Collaborative Computation in Self-Organizing Particle Systems

## 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(**bits. 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

*n*)**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(**asynchronous rounds and multiply an

*v*)

**h***x*

*matrix by a*

**w***x*

**w****1**vector in

**O(**asynchronous rounds.

*h*+*w*)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).