Non-local Probes Do Not Help with Many Graph Problems

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

doi:10.1007/978-3-662-53426-7_15

Non-local Probes Do Not Help with Many Graph Problems

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

11 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äiskieli	Englanti
Otsikko	Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings
Toimittajat	Cyril Gavoille, David Ilcinkas
Julkaisupaikka	Berlin, Heidelberg
Kustantaja	Springer
Sivut	201-214
Sivumäärä	14
Vuosikerta	9888 LNCS
ISBN (painettu)	9783662534250
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-662-53426-7_15
Tila	Julkaistu - 2016
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Symposium on Distributed Computing - Paris, Ranska Kesto: 27 syysk. 2016 → 29 syysk. 2016 Konferenssinumero: 30 http://www.disc-conference.org/wp/disc2016/

Julkaisusarja

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

Conference

Conference	International Symposium on Distributed Computing
Lyhennettä	DISC 2016
Maa/Alue	Ranska
Kaupunki	Paris
Ajanjakso	27/09/2016 → 29/09/2016
www-osoite	http://www.disc-conference.org/wp/disc2016/

Pääsy asiakirjaan

10.1007/978-3-662-53426-7_15

http://dx.doi.org/10.1007/978-3-662-53426-7_15

OpenUrl-saatavuus

Koko teksti

Siteeraa tätä

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

Göös, Mika ; Hirvonen, Juho ; Levi, Reut et al. / Non-local Probes Do Not Help with Many Graph Problems. Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings. Toimittaja / Cyril Gavoille ; David Ilcinkas. Vuosikerta 9888 LNCS Berlin, Heidelberg : Springer, 2016. Sivut 201-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ada6dd927dc74a32865f1d7ee70ce798,

title = "Non-local Probes Do Not Help with Many Graph Problems",

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.",

author = "Mika G{\"o}{\"o}s and Juho Hirvonen and Reut Levi and Moti Medina and Jukka Suomela",

year = "2016",

doi = "10.1007/978-3-662-53426-7_15",

language = "English",

isbn = "9783662534250",

volume = "9888 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "201--214",

editor = "Cyril Gavoille and David Ilcinkas",

booktitle = "Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings",

address = "Germany",

note = "International Symposium on Distributed Computing, DISC 2016 ; Conference date: 27-09-2016 Through 29-09-2016",

url = "http://www.disc-conference.org/wp/disc2016/",

}

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

Non-local Probes Do Not Help with Many Graph Problems. / Göös, Mika; Hirvonen, Juho; Levi, Reut et al.
Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings. toim. / Cyril Gavoille; David Ilcinkas. Vuosikerta 9888 LNCS Berlin, Heidelberg: Springer, 2016. s. 201-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 9888 LNCS).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

TY - GEN

T1 - Non-local Probes Do Not Help with Many Graph Problems

AU - Göös, Mika

AU - Hirvonen, Juho

AU - Levi, Reut

AU - Medina, Moti

AU - Suomela, Jukka

N1 - Conference code: 30

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-53426-7_15

DO - 10.1007/978-3-662-53426-7_15

M3 - Conference contribution

SN - 9783662534250

VL - 9888 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 201

EP - 214

BT - Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings

A2 - Gavoille, Cyril

A2 - Ilcinkas, David

PB - Springer

CY - Berlin, Heidelberg

T2 - International Symposium on Distributed Computing

Y2 - 27 September 2016 through 29 September 2016

ER -

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

Non-local Probes Do Not Help with Many Graph Problems

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Sormenjälki

Siteeraa tätä