Organizing a Global Coordinate System from Local Information on an Amorphous Computer
This paper demonstrates that it is possible to generate a reasonably accurate coordinate system on randomly distributed processors, using only local information and local communication. By coordinate systems we imply that each element assigns itself a logical coordinate that maps to its global...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5926 |
| _version_ | 1811088678278135808 |
|---|---|
| author | Nagpal, Radhika |
| author_facet | Nagpal, Radhika |
| author_sort | Nagpal, Radhika |
| collection | MIT |
| description | This paper demonstrates that it is possible to generate a reasonably accurate coordinate system on randomly distributed processors, using only local information and local communication. By coordinate systems we imply that each element assigns itself a logical coordinate that maps to its global physical location, starting with no apriori knowledge of position or orientation. The algorithm presented is inspired by biological systems that use chemical gradients to determine the position of cells. Extensive analysis and simulation results are presented. Two key results are: there is a critical minimum average neighborhood size of 15 for good accuracy and there is a fundamental limit on the resolution of any coordinate system determined strictly from local communication. We also demonstrate that using this algorithm, random distributions of processors produce significantly better accuracy than regular processor grids - such as those used by cellular automata. This has implications for discrete models of biology as well as for building smart sensor arrays. |
| first_indexed | 2024-09-23T14:05:48Z |
| id | mit-1721.1/5926 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:05:48Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/59262019-04-10T17:24:19Z Organizing a Global Coordinate System from Local Information on an Amorphous Computer Nagpal, Radhika AI MIT Artificial Intelligence Amorphous Computing Cellular Automata Coordinate Systems Self-Organization Chemical Gradients Global Local This paper demonstrates that it is possible to generate a reasonably accurate coordinate system on randomly distributed processors, using only local information and local communication. By coordinate systems we imply that each element assigns itself a logical coordinate that maps to its global physical location, starting with no apriori knowledge of position or orientation. The algorithm presented is inspired by biological systems that use chemical gradients to determine the position of cells. Extensive analysis and simulation results are presented. Two key results are: there is a critical minimum average neighborhood size of 15 for good accuracy and there is a fundamental limit on the resolution of any coordinate system determined strictly from local communication. We also demonstrate that using this algorithm, random distributions of processors produce significantly better accuracy than regular processor grids - such as those used by cellular automata. This has implications for discrete models of biology as well as for building smart sensor arrays. 2004-10-04T14:15:18Z 2004-10-04T14:15:18Z 1999-08-29 AIM-1666 http://hdl.handle.net/1721.1/5926 en_US AIM-1666 12 p. 13431639 bytes 426245 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | AI MIT Artificial Intelligence Amorphous Computing Cellular Automata Coordinate Systems Self-Organization Chemical Gradients Global Local Nagpal, Radhika Organizing a Global Coordinate System from Local Information on an Amorphous Computer |
| title | Organizing a Global Coordinate System from Local Information on an Amorphous Computer |
| title_full | Organizing a Global Coordinate System from Local Information on an Amorphous Computer |
| title_fullStr | Organizing a Global Coordinate System from Local Information on an Amorphous Computer |
| title_full_unstemmed | Organizing a Global Coordinate System from Local Information on an Amorphous Computer |
| title_short | Organizing a Global Coordinate System from Local Information on an Amorphous Computer |
| title_sort | organizing a global coordinate system from local information on an amorphous computer |
| topic | AI MIT Artificial Intelligence Amorphous Computing Cellular Automata Coordinate Systems Self-Organization Chemical Gradients Global Local |
| url | http://hdl.handle.net/1721.1/5926 |
| work_keys_str_mv | AT nagpalradhika organizingaglobalcoordinatesystemfromlocalinformationonanamorphouscomputer |