
We study the problem of distributed task allocation inspired by the behavior
of social insects, which perform task allocation in a setting of limited
capabilities and noisy environment feedback. We assume that each task has a
demand that should be satisfied but not exceeded, i.e., there is an optimal
number of ants that should be working on this task at a given time. The goal is
to assign a nearoptimal number of workers to each task in a distributed manner
and without explicit access to the values of the demands nor the number of ants
working on the task.
We seek to answer the question of how the quality of task allocation depends
on the accuracy of assessing whether too many (overload) or not enough (lack)
ants are currently working on a given task. Concretely, we address the open
question of solving task allocation in the model where each ant receives
feedback that depends on the deficit defined as the (possibly negative)
difference between the optimal demand and the current number of workers in the
task. The feedback is modeled as a random variable that takes value lack or
overload with probability given by a sigmoid of the deficit. Each ants receives
the feedback independently, but the higher the overload or lack of workers for
a task, the more likely it is that all the ants will receive the same, correct
feedback from this task; the closer the deficit is to zero, the less reliable
the feedback becomes. We measure the performance of task allocation algorithms
using the notion of regret, defined as the absolute value of the deficit summed
over all tasks and summed over time.
We propose a simple, constantmemory, selfstabilizing, distributed algorithm
that quickly converges from any initial distribution to a nearoptimal
assignment. We also show that our algorithm works not only under stochastic
noise but also in an adversarial noise setting.

We introduce the study of the ant colony househunting 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 househunting process.
We develop a formal model for the househunting problem inspired by the
behavior of the Temnothorax genus of ants. We then show a \Omega(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 househunting 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.

We consider the ANTS problem [Feinerman et al.] in which a group of agents
collaboratively search for a target in a twodimensional 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 $\chi$, defined for
algorithm ${\cal A}$ such that $\chi({\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 tradeoff between the standard performance metric of
speedup, 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 subexponential 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
nearoptimal speedup of $(D^2/n +D) \cdot 2^{O(\ell)}$ for $\chi({\cal A})
\leq 3 \log \log D + O(1)$. In particular, for $\ell \in O(1)$, the speedup is
asymptotically optimal. By comparison, the existing results for this problem
[Feinerman et al.] that achieve similar speedup require $\chi({\cal A}) =
\Omega(\log D)$. We then show that this threshold is tight by describing a
lower bound showing that if $\chi({\cal A}) < \log \log D  \omega(1)$, then
with high probability the target is not found within $D^{2o(1)}$ moves per
agent. Hence, there is a sizable gap to the straightforward $\Omega(D^2/n + D)$
lower bound in this setting.