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.

DOI

https://doi.org/10.31274/etd-180810-1532

Copyright Owner

Neeraj S. Khanolkar

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

50 pages

Download

Share

COinS