Degree Type
Thesis
Date of Award
2009
Degree Name
Master of Science
Department
Computer Science
First Advisor
Soma Chaudhuri
Abstract
Multi-agent stigmergy forms the basis of explanatory theories for various self-organized biological phenomena, and also serves as an implementation strategy for several important artificial applications. While a number of sophisticated techniques have been used in the modeling and analysis of stigmergic processes, none of them, yet, seem to be drawn from the toolbox of classical distributed computing. Our goals are to investigate and lay the groundwork for the use of classical distributed computing ideas in reasoning about stigmergic computation.
Specifically, we investigate case studies that are drawn from the domain of binary matrix pattern sorting. Here, a `swarm' of memory-less and non-communicating agents follow a set of local stigmergic rules to asynchronously sort the binary states of cells in a 2-D grid so as to satisfy some global pattern specification. This domain is attractive as a test-bed because it serves as an abstraction for instances of biological pattern sorting and also because of its stigmergic expressiveness.
We demonstrate the application of the following four distributed computing concepts: (1) execution serializability, (2) local checking, (3) variant functions, and (4) indistinguishability (the last as an impossibility proof technique) in the modeling and analysis of our case studies.
Based on our preliminary experience with this particular domain, it seems to us that classical distributed computing techniques could be applied further in reasoning about stigmergic systems, perhaps leading to the formulation of a generalized stigmergic computational paradigm based on the principles of distributed computing.
Copyright Owner
Neeraj S. Khanolkar
Copyright Date
2009
Language
en
Date Available
2012-04-30
File Format
application/pdf
File Size
50 pages
Recommended Citation
Khanolkar, Neeraj S., "Asynchronous stigmergic sorting of binary matrix patterns: applications of classical distributed computing ideas" (2009). Graduate Theses and Dissertations. 11111.
https://lib.dr.iastate.edu/etd/11111