{"id":1036,"date":"2024-04-02T10:10:48","date_gmt":"2024-04-02T17:10:48","guid":{"rendered":"https:\/\/labs.engineering.asu.edu\/sops\/?page_id=1036"},"modified":"2024-04-02T10:10:48","modified_gmt":"2024-04-02T17:10:48","slug":"collaborative-computation","status":"publish","type":"page","link":"https:\/\/labs.engineering.asu.edu\/sops\/collaborative-computation\/","title":{"rendered":"Collaborative Computation in Self-Organizing Particle Systems"},"content":{"rendered":"\n
<\/div>\n\n\n\n
\n
\n

Alexandra Porter and\u00a0Andr\u00e9a W. Richa.
[arXiv<\/a>] [Online<\/a>] \u2014 Conference paper in\u00a0Unconventional Computation and Natural Computation \u2013 17th International Conference (UCNC \u201918),\u00a0<\/em>pp. 188-203, 2018.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Overview<\/h2>\n\n\n\n

The amoebot model constrains each particle to only a constant-size memory, meaning particles can\u2019t store values that depend in any way on the size of the system. Even counting the number of particles in the system (say n<\/strong><\/em>) requires log(n<\/em>) <\/strong>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 increment-only binary counter<\/strong> and then use these counters to achieve matrix-vector multiplication<\/strong>. We prove that our algorithms count to a value v<\/strong><\/em> <\/em>in O(v<\/em>) <\/strong>asynchronous rounds and multiply an h<\/strong><\/em> <\/em>x w<\/strong><\/em> matrix by a w<\/strong><\/em> x 1<\/strong> vector in O(h <\/em>+ w<\/em>) <\/strong>asynchronous rounds.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n
\"\"<\/figure>\n<\/div>\n\n\n\n
\n
\"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

To demonstrate these primitives\u2019 utility, we show how they can be used by self-organizing particle systems to implement image processing algorithms.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Resources<\/h2>\n\n\n\n

None.<\/p>\n\n\n\n

Press<\/h2>\n\n\n\n

None.<\/p>\n\n\n\n

BibTeX<\/h2>\n\n\n\n

@InProceedings{Porter2018,
title = {Collaborative Computation in Self-Organizing Particle Systems},
Author = {Porter, Alexandra and Richa, Andr\u00e9a W.},
Booktitle = {Unconventional Computation and Natural Computation},
Series = {UCNC ’18},
Pages = {188–203},
Year = {2018} }<\/p>\n\n\n\n

Related Publications<\/h2>\n\n\n\n

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<\/a> (2019).<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Alexandra Porter and\u00a0Andr\u00e9a W. Richa.[arXiv] [Online] \u2014 Conference paper in\u00a0Unconventional Computation and Natural Computation \u2013 17th International Conference (UCNC \u201918),\u00a0pp. 188-203, 2018. Overview The amoebot model constrains each particle to only a constant-size memory, meaning particles can\u2019t store values that depend in any way on the size of the system. Even counting the number of…<\/p>\n","protected":false},"author":338,"featured_media":0,"parent":0,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"footnotes":""},"class_list":["post-1036","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/pages\/1036","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/users\/338"}],"replies":[{"embeddable":true,"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/comments?post=1036"}],"version-history":[{"count":0,"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/pages\/1036\/revisions"}],"wp:attachment":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/media?parent=1036"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}