Notice
This is not the latest version of this item. The latest version can be found at:https://dspace.mit.edu/handle/1721.1/137563.2
Self-Stabilizing Task Allocation In Spite of Noise
Author(s)
Dornhaus, Anna; Lynch, Nancy; Mallmann-Trenn, Frederik; Pajak, Dominik; Radeva, Tsvetomira![Thumbnail](/bitstream/handle/1721.1/137563/1805.03691.pdf.jpg?sequence=4&isAllowed=y)
DownloadSubmitted version (818.5Kb)
Open Access Policy
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
© 2020 ACM. We study the problem of distributed task allocation by workers in an ant colony 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 near-optimal number of workers to each task in a distributed manner without explicit access to the value of the demand nor to 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 by the ants whether too many (overload) or not enough (lack) ants are currently working on a given task. In our model, each ant receives a binary feedback that depends on the deficit, defined as the difference between the demand and the current number of workers in the task. The feedback is modeled as a random variable that takes values lack or overload with probability given by a sigmoid function of the deficit. The higher the overload or lack of workers for a task, the more likely it is that an ant receives the correct feedback from this task; the closer the deficit is to zero, the less reliable the feedback becomes. Each ant receives the feedback independently about one chosen task. We measure the performance of task allocation algorithms using the notion of inaccuracy, defined as the number of steps in which the deficit of some task is beyond certain threshold. We propose a simple, constant-memory, self-stabilizing, distributed algorithm that converges from any initial assignment to a near-optimal assignment under noisy feedback and keeps the deficit small for all tasks in almost every step. We also prove a lower bound for any constant-memory algorithm, which matches, up to a constant factor, the accuracy achieved by our algorithm.
Date issued
2020Journal
Annual ACM Symposium on Parallelism in Algorithms and Architectures
Publisher
Association for Computing Machinery (ACM)
Citation
Dornhaus, Anna, Lynch, Nancy, Mallmann-Trenn, Frederik, Pajak, Dominik and Radeva, Tsvetomira. 2020. "Self-Stabilizing Task Allocation In Spite of Noise." Annual ACM Symposium on Parallelism in Algorithms and Architectures.
Version: Original manuscript