An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer
Amorphous computing is the study of programming ultra-scale computing environments of smart sensors and actuators cite{white-paper}. The individual elements are identical, asynchronous, randomly placed, embedded and communicate locally via wireless broadcast. Aggregating the processors into groups i...
| Main Authors: | , |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6669 |
| _version_ | 1826200655912501248 |
|---|---|
| author | Nagpal, Radhika Coore, Daniel |
| author_facet | Nagpal, Radhika Coore, Daniel |
| author_sort | Nagpal, Radhika |
| collection | MIT |
| description | Amorphous computing is the study of programming ultra-scale computing environments of smart sensors and actuators cite{white-paper}. The individual elements are identical, asynchronous, randomly placed, embedded and communicate locally via wireless broadcast. Aggregating the processors into groups is a useful paradigm for programming an amorphous computer because groups can be used for specialization, increased robustness, and efficient resource allocation. This paper presents a new algorithm, called the clubs algorithm, for efficiently aggregating processors into groups in an amorphous computer, in time proportional to the local density of processors. The clubs algorithm is well-suited to the unique characteristics of an amorphous computer. In addition, the algorithm derives two properties from the physical embedding of the amorphous computer: an upper bound on the number of groups formed and a constant upper bound on the density of groups. The clubs algorithm can also be extended to find the maximal independent set (MIS) and $Delta + 1$ vertex coloring in an amorphous computer in $O(log N)$ rounds, where $N$ is the total number of elements and $Delta$ is the maximum degree. |
| first_indexed | 2024-09-23T11:39:48Z |
| id | mit-1721.1/6669 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:39:48Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/66692019-04-12T08:31:45Z An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer Nagpal, Radhika Coore, Daniel Amorphous computing is the study of programming ultra-scale computing environments of smart sensors and actuators cite{white-paper}. The individual elements are identical, asynchronous, randomly placed, embedded and communicate locally via wireless broadcast. Aggregating the processors into groups is a useful paradigm for programming an amorphous computer because groups can be used for specialization, increased robustness, and efficient resource allocation. This paper presents a new algorithm, called the clubs algorithm, for efficiently aggregating processors into groups in an amorphous computer, in time proportional to the local density of processors. The clubs algorithm is well-suited to the unique characteristics of an amorphous computer. In addition, the algorithm derives two properties from the physical embedding of the amorphous computer: an upper bound on the number of groups formed and a constant upper bound on the density of groups. The clubs algorithm can also be extended to find the maximal independent set (MIS) and $Delta + 1$ vertex coloring in an amorphous computer in $O(log N)$ rounds, where $N$ is the total number of elements and $Delta$ is the maximum degree. 2004-10-08T20:37:02Z 2004-10-08T20:37:02Z 1998-02-01 AIM-1626 http://hdl.handle.net/1721.1/6669 en_US AIM-1626 2177371 bytes 452206 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Nagpal, Radhika Coore, Daniel An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer |
| title | An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer |
| title_full | An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer |
| title_fullStr | An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer |
| title_full_unstemmed | An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer |
| title_short | An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer |
| title_sort | algorithm for group formation and maximal independent set in an amorphous computer |
| url | http://hdl.handle.net/1721.1/6669 |
| work_keys_str_mv | AT nagpalradhika analgorithmforgroupformationandmaximalindependentsetinanamorphouscomputer AT cooredaniel analgorithmforgroupformationandmaximalindependentsetinanamorphouscomputer AT nagpalradhika algorithmforgroupformationandmaximalindependentsetinanamorphouscomputer AT cooredaniel algorithmforgroupformationandmaximalindependentsetinanamorphouscomputer |