Frederik Mallmann-Trenn: Self-Stabilizing Task Allocation in Spite of Noise

Friday, March 9, 2018 - 1:00pm to 2:30pm
Frederik Mallmann-Trenn
We study the problem of distributed task allocation inspired by the behavior of various ant species, which are known to perform task allocation efficiently in a setting of limited capabilities and noisy environment feedback. We seek to answer the question of how the quality of task allocation depends on the accuracy of detecting lack and surplus of workers in the tasks.
We assume that each task that needs to be done by the ant colony has a \emph{demand}, i.e., the optimal number of ants that should be working on this task. The goal is to assign a set of workers of near-optimal size to each task in a distributed manner and without access to the real values of the demands.
Concretely, we address the open question of solving task allocation in the model where each ant receives binary feedback 
that depends on the \emph{deficit}, i.e., the difference between the optimal demand and the current number of workers in the task. The feedback is modeled as a binary random variable that takes value $lack$ with probability given by a sigmoid of the deficit and $surplus$ otherwise. The higher the overload or lack of workers for a task, the more likely it is that ants will receive the correct feedback; the closer the deficit is to zero, the ``fuzzier'' the feedback becomes. We measure the performance of task allocation algorithms using the notion of \emph{regret}, defined as the absolute value of the deficit summed over all tasks.
Our main results is a simple, self-stabilizing, constant-memory, distributed algorithm that achieves, up to a constant factor, the optimal regret. Moreover the algorithm quickly converges from any initial distribution to a near-optimal assignment even in a more adversarial noise setting.