Source author record

Moshe Sulamy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Idle Ants Have a Role

Using elementary distributed computing techniques we suggest an explanation for two unexplained phenomena in regards to ant colonies, (a) a substantial amount of ants in an ant colony are idle, and (b) the observed low survivability of new ant colonies in nature. Ant colonies employ task allocation, in which ants progress from one task to the other, to meet changing demands introduced by the environment. Extending the biological task allocation model given in [Pacala, Gordon and Godfray 1996] we present a distributed algorithm which mimics the mechanism ants use to solve task allocation efficiently in nature. Analyzing the time complexity of the algorithm reveals an exponential gap on the time it takes an ant colony to satisfy a certain work demand with and without idle ants. We provide an $O(\ln n)$ upper bound when a constant fraction of the colony are idle ants, and a contrasting lower bound of $Ω(n)$ when there are no idle ants, where $n$ is the total number of ants in the colony.

preprint2015arXiv

Optimal and Resilient Pheromone Utilization in Ant Foraging

Pheromones are a chemical substance produced and released by ants as means of communication. In this work we present the minimum amount of pheromones necessary and sufficient for a colony of ants (identical mobile agents) to deterministically find a food source (treasure), assuming that each ant has the computational capabilities of either a Finite State Machine (FSM) or a Turing Machine (TM). In addition, we provide pheromone-based foraging algorithms capable of handling fail-stop faults. In more detail, we consider the case where $k$ identical ants, initially located at the center (nest) of an infinite two-dimensional grid and communicate only through pheromones, perform a collaborative search for an adversarially hidden treasure placed at an unknown distance $D$ . We begin by proving a tight lower bound of $Ω(D)$ on the amount of pheromones required by any number of FSM based ants to complete the search, and continue to reduce the lower bound to $Ω(k)$ for the stronger ants modeled as TM. We provide algorithms which match the aforementioned lower bounds, and still terminate in optimal $\mathcal{O}(D + D^2 / k)$ time, under both the synchronous and asynchronous models. Furthermore, we consider a more realistic setting, where an unknown number $f < k$ of ants may fail-stop at any time; we provide fault-tolerant FSM algorithms (synchronous and asynchronous), that terminate in $\mathcal{O}(D + D^2/(k-f) + Df)$ rounds and emit no more than the same asymptotic minimum number of $\mathcal{O}(D)$ pheromones overall.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.