Mika Göös · Juho Hirvonen · Reut Levi · Moti Medina · Jukka Suomela

Non-local probes do not help with many graph problems

DISC 2016 · 30th International Symposium on Distributed Computing, Paris, France, September 2016 · doi:10.1007/978-3-662-53426-7_15

authors’ version publisher’s version arXiv.org

Abstract

This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.

Publication

Cyril Gavoille and David Ilcinkas (Eds.): Distributed Computing, 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016, Proceedings, volume 9888 of Lecture Notes in Computer Science, Springer, Berlin, 2016

ISBN 978-3-662-53425-0

Links

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.