M.S. Thesis Defense - Neeraj Khanolkar

Date: 18 Aug, 2009
Time: 10:00 AM
Location: 223 Atanasoff Hall
Topic: Using Classical Distributed Computing Ideas in the Modeling and Analysis of Stigmergic Processes: some case studies
Major Professor(s): 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 serializabiltiy, (2) local checking, (3) variant functions, and (4) indistinguishability (the last as an impossibility proof technique) in the modeling and analysis of the 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.