Non-local Probes Do Not Help with Many Graph Problems

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

7 Sitaatiot (Scopus)

Abstrakti

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.
AlkuperäiskieliEnglanti
OtsikkoDistributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings
ToimittajatCyril Gavoille, David Ilcinkas
JulkaisupaikkaBerlin, Heidelberg
KustantajaSpringer Berlin Heidelberg
Sivut201-214
Sivumäärä14
Vuosikerta9888 LNCS
ISBN (painettu)9783662534250
DOI - pysyväislinkit
TilaJulkaistu - 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Distributed Computing - Paris, Ranska
Kesto: 27 syyskuuta 201629 syyskuuta 2016
Konferenssinumero: 30
http://www.disc-conference.org/wp/disc2016/

Julkaisusarja

NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta9888 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC 2016
MaaRanska
KaupunkiParis
Ajanjakso27/09/201629/09/2016
www-osoite

Sormenjälki Sukella tutkimusaiheisiin 'Non-local Probes Do Not Help with Many Graph Problems'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä