Abstract

We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(^5) rounds in graphs of maximum degree , while we improve it to O(^4) and also prove a lower bound of ω(). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.

Original languageEnglish
Title of host publicationSPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery (ACM)
Pages129-139
Number of pages11
ISBN (Electronic)9781450380706
DOIs
Publication statusPublished - 6 Jul 2021
MoE publication typeA4 Article in a conference publication
EventAnnual ACM Symposium on Parallelism in Algorithms and Architectures - Virtual, Online, United States
Duration: 6 Jul 20218 Jul 2021

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

ConferenceAnnual ACM Symposium on Parallelism in Algorithms and Architectures
Abbreviated titleSPAA
Country/TerritoryUnited States
CityVirtual, Online
Period06/07/202108/07/2021

Keywords

  • Distributed graph algorithms
  • Load balancing
  • Semi-matching
  • Stable orientations

Fingerprint

Dive into the research topics of 'Efficient load-balancing through distributed token dropping'. Together they form a unique fingerprint.

Cite this