Self-Stabilizing Task Allocation In Spite of Noise
© 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 wo...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137563 |
| _version_ | 1826211540358922240 |
|---|---|
| author | Dornhaus, Anna Lynch, Nancy Mallmann-Trenn, Frederik Pajak, Dominik Radeva, Tsvetomira |
| author_facet | Dornhaus, Anna Lynch, Nancy Mallmann-Trenn, Frederik Pajak, Dominik Radeva, Tsvetomira |
| author_sort | Dornhaus, Anna |
| collection | MIT |
| description | © 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. |
| first_indexed | 2024-09-23T15:07:38Z |
| format | Article |
| id | mit-1721.1/137563 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:07:38Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1375632022-10-02T00:45:29Z Self-Stabilizing Task Allocation In Spite of Noise Dornhaus, Anna Lynch, Nancy Mallmann-Trenn, Frederik Pajak, Dominik Radeva, Tsvetomira © 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. 2021-11-05T18:26:02Z 2021-11-05T18:26:02Z 2020 2021-01-29T15:16:58Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137563 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. en 10.1145/3350755.3400226 Annual ACM Symposium on Parallelism in Algorithms and Architectures Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Dornhaus, Anna Lynch, Nancy Mallmann-Trenn, Frederik Pajak, Dominik Radeva, Tsvetomira Self-Stabilizing Task Allocation In Spite of Noise |
| title | Self-Stabilizing Task Allocation In Spite of Noise |
| title_full | Self-Stabilizing Task Allocation In Spite of Noise |
| title_fullStr | Self-Stabilizing Task Allocation In Spite of Noise |
| title_full_unstemmed | Self-Stabilizing Task Allocation In Spite of Noise |
| title_short | Self-Stabilizing Task Allocation In Spite of Noise |
| title_sort | self stabilizing task allocation in spite of noise |
| url | https://hdl.handle.net/1721.1/137563 |
| work_keys_str_mv | AT dornhausanna selfstabilizingtaskallocationinspiteofnoise AT lynchnancy selfstabilizingtaskallocationinspiteofnoise AT mallmanntrennfrederik selfstabilizingtaskallocationinspiteofnoise AT pajakdominik selfstabilizingtaskallocationinspiteofnoise AT radevatsvetomira selfstabilizingtaskallocationinspiteofnoise |