Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems

Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. 2014. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. PODC: Principles of Distributed Computing, 232–241.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Alistarh, Dan-AdrianIST Austria; Denysyuk, Oksana; Rodrígues, Luís; Shavit, Nir
Abstract
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 ©(logn) 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 sublogarithmic 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) rounds w.h.p., where 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.
Publishing Year
Date Published
2014-01-01
Acknowledgement
Dan Alistarh was partially supported by the SNF Post- doctoral Fellows Program, NSF grant CCF-1217921, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations. Oksana Denysyuk and Lu ́ıs Rodrigues were partially supported by Funda ̧c ̃ao para a Ciˆencia e Tecnologia (FCT) via the project PEPITA (PTDC/EEI-SCR/2776/2012) and via the INESC-ID multi-annual funding through the PIDDAC Program fund grant, under project PEst-OE/EEI/LA0021/ 2013. Nir Shavit was supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.
Page
232 - 241
Conference
PODC: Principles of Distributed Computing
IST-REx-ID
771

Cite this

Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. In: ACM; 2014:232-241. doi:10.1145/2611462.2611499
Alistarh, D.-A., Denysyuk, O., Rodrígues, L., & Shavit, N. (2014). Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems (pp. 232–241). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2611462.2611499
Alistarh, Dan-Adrian, Oksana Denysyuk, Luís Rodrígues, and Nir Shavit. “Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems,” 232–41. ACM, 2014. https://doi.org/10.1145/2611462.2611499.
D.-A. Alistarh, O. Denysyuk, L. Rodrígues, and N. Shavit, “Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems,” presented at the PODC: Principles of Distributed Computing, 2014, pp. 232–241.
Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. 2014. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. PODC: Principles of Distributed Computing, 232–241.
Alistarh, Dan-Adrian, et al. Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems. ACM, 2014, pp. 232–41, doi:10.1145/2611462.2611499.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar