Deterministic Expander Routing: Faster and More Versatile
Part Of
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Start Page
194
End Page
204
ISBN (of the container)
979-840070668-4
Date Issued
2024-06-17
Author(s)
Abstract
We consider the expander routing problem formulated by Ghaffari, Kuhn, and Su (PODC 2017), where the goal is to route all the tokens to their destinations given that each vertex is the source and the destination of at most deg(υ) tokens. They developed randomized algorithms that solve this problem in poly [EQUATION] rounds in the CONGEST model, where ϕ is the conductance of the graph. In addition, as noted by Chang, Pettie, Saranurak, and Zhang (JACM 2021), it is possible to obtain a preprocessing/query tradeoff so that the routing queries can be answered faster at the cost of more preprocessing time. The efficiency and flexibility of the processing/query tradeoff of expander routing have led to many other distributed algorithms in the CONGEST model, such as subpolynomial-round minimum spanning tree algorithms in expander graphs and near-optimal algorithms for k-clique enumeration in general graphs.
Event(s)
43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2024
Publisher
ACM
Type
conference paper