Mika Göös · Juho Hirvonen · Jukka Suomela

Linear-in-Δ lower bounds in the LOCAL model

PODC 2014 · 33rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Paris, France, July 2014 · doi:10.1145/2611462.2611467

authors’ version publisher’s version arXiv.org

Abstract

By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in O(Δ) rounds, where Δ is the maximum degree of the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in o(Δ) rounds.

Our work gives the first linear-in-Δ lower bound for a natural graph problem in the standard model of distributed computing—prior lower bounds for a wide range of graph problems have been at best logarithmic in Δ.

Publication

Magnús Halldórsson and Shlomi Dolev (Eds.): PODC’14, Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, July 15–18, 2014, Paris, France, pages 86–95, ACM Press, New York, 2014

ISBN 978-1-4503-2944-6

Links

Journal Version

© Göös et al. 2014. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive version was published in Proc. PODC 2014.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.