Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems
We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in sy...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101056 https://orcid.org/0000-0002-4552-2414 |
| _version_ | 1826217479546863616 |
|---|---|
| author | Alistarh, Dan Denysyuk, Oksana Shavit, Nir N. Rodrigues, Luis |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Alistarh, Dan Denysyuk, Oksana Shavit, Nir N. Rodrigues, Luis |
| author_sort | Alistarh, Dan |
| collection | MIT |
| description | We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Θ(log n) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sub-logarithmic solutions exist for this apparently simple but intriguing problem.
In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O(log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict.
We then extend the algorithm to terminate early in O(log log f) rounds w.h.p., where f is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems. |
| first_indexed | 2024-09-23T17:04:18Z |
| format | Article |
| id | mit-1721.1/101056 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:04:18Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1010562022-10-03T10:12:28Z Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems Alistarh, Dan Denysyuk, Oksana Shavit, Nir N. Rodrigues, Luis Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shavit, Nir N. We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Θ(log n) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sub-logarithmic solutions exist for this apparently simple but intriguing problem. In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O(log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. We then extend the algorithm to terminate early in O(log log f) rounds w.h.p., where f is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems. National Science Foundation (U.S.) (Grant CCF-1217921) National Science Foundation (U.S.) (Grant CCF-1301926) United States. Dept. of Energy (Advanced Scientific Computing Research Grant ER26116/DE-SC0008923) Oracle Corporation Intel Corporation 2016-02-02T02:42:54Z 2016-02-02T02:42:54Z 2014-07 Article http://purl.org/eprint/type/ConferencePaper 9781450329446 http://hdl.handle.net/1721.1/101056 Dan Alistarh, Oksana Denysyuk, Luis Rodrigues, and Nir Shavit. 2014. Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC '14). ACM, New York, NY, USA, 232-241. https://orcid.org/0000-0002-4552-2414 en_US http://dx.doi.org/10.1145/2611462.2611499 Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC '14) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Alistarh, Dan Denysyuk, Oksana Shavit, Nir N. Rodrigues, Luis Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems |
| title | Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems |
| title_full | Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems |
| title_fullStr | Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems |
| title_full_unstemmed | Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems |
| title_short | Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems |
| title_sort | balls into leaves sub logarithmic renaming in synchronous message passing systems |
| url | http://hdl.handle.net/1721.1/101056 https://orcid.org/0000-0002-4552-2414 |
| work_keys_str_mv | AT alistarhdan ballsintoleavessublogarithmicrenaminginsynchronousmessagepassingsystems AT denysyukoksana ballsintoleavessublogarithmicrenaminginsynchronousmessagepassingsystems AT shavitnirn ballsintoleavessublogarithmicrenaminginsynchronousmessagepassingsystems AT rodriguesluis ballsintoleavessublogarithmicrenaminginsynchronousmessagepassingsystems |