Source author record

Tsvetomira Radeva

Tsvetomira Radeva appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing

Catalog footprint

What is connected

2works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2015arXiv

Distributed House-Hunting in Ant Colonies

We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony must relocate to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. The ants must additionally reach consensus on a final nest choice and the full colony must be transported to this single new nest. Our goal is to use tools and techniques from distributed computing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Ω(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest.

preprint2014arXiv

Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication

We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the behavior of biological species, we argue that in addition to studying the {\em time complexity} of solutions it is also important to study the {\em selection complexity}, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. In more detail, we propose a new selection complexity metric $χ$, defined for algorithm ${\cal A}$ such that $χ({\cal A}) = b + \log \ell$, where $b$ is the number of memory bits used by each agent and $\ell$ bounds the fineness of available probabilities (agents use probabilities of at least $1/2^\ell$). In this paper, we study the trade-off between the standard performance metric of speed-up, which measures how the expected time to find the target improves with $n$, and our new selection metric. In particular, consider $n$ agents searching for a treasure located at (unknown) distance $D$ from the origin (where $n$ is sub-exponential in $D$). For this problem, we identify $\log \log D$ as a crucial threshold for our selection complexity metric. We first prove a new upper bound that achieves a near-optimal speed-up of $(D^2/n +D) \cdot 2^{O(\ell)}$ for $χ({\cal A}) \leq 3 \log \log D + O(1)$. In particular, for $\ell \in O(1)$, the speed-up is asymptotically optimal. By comparison, the existing results for this problem [Feinerman et al.] that achieve similar speed-up require $χ({\cal A}) = Ω(\log D)$. We then show that this threshold is tight by describing a lower bound showing that if $χ({\cal A}) < \log \log D - ω(1)$, then with high probability the target is not found within $D^{2-o(1)}$ moves per agent. Hence, there is a sizable gap to the straightforward $Ω(D^2/n + D)$ lower bound in this setting.