Non-local Probes Do Not Help with Many Graph Problems

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

7 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationDistributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings
EditorsCyril Gavoille, David Ilcinkas
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Pages201-214
Number of pages14
Volume9888 LNCS
ISBN (Print)9783662534250
DOIs
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - Paris, France
Duration: 27 Sep 201629 Sep 2016
Conference number: 30
http://www.disc-conference.org/wp/disc2016/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9888 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC 2016
CountryFrance
CityParis
Period27/09/201629/09/2016
Internet address

Fingerprint Dive into the research topics of 'Non-local Probes Do Not Help with Many Graph Problems'. Together they form a unique fingerprint.

  • Cite this

    Göös, M., Hirvonen, J., Levi, R., Medina, M., & Suomela, J. (2016). Non-local Probes Do Not Help with Many Graph Problems. In C. Gavoille, & D. Ilcinkas (Eds.), Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings (Vol. 9888 LNCS, pp. 201-214). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9888 LNCS). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-53426-7_15