Ability to count messages is worth Θ(Δ) rounds in distributed computing

Tuomo Lempiäinen

doi:10.1145/2933575.2934567

Ability to count messages is worth Θ(Δ) rounds in distributed computing

Tuomo Lempiäinen

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

Abstract

Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing – one of which is the port-numbering model – and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2Δ–2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Δ lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.

Original language	English
Title of host publication	Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
Place of Publication	New York, NY, USA
Publisher	ACM
Pages	357-366
ISBN (Electronic)	978-1-4503-4391-6
DOIs	https://doi.org/10.1145/2933575.2934567
Publication status	Published - 5 Jul 2016
MoE publication type	A4 Conference publication
Event	Annual ACM/IEEE Symposium on Logic in Computer Science - New York, United States Duration: 5 Jul 2016 → 8 Jul 2016 Conference number: 31

Publication series

Name	Annual ACM/IEEE Symposium on Logic in Computer Science
Publisher	ACM/IEEE
ISSN (Print)	1043-6871

Conference

Conference	Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated title	LICS
Country/Territory	United States
City	New York
Period	05/07/2016 → 08/07/2016

Keywords

distributed computing
port-numbering model
local algorithms
lower bounds
bisimulation

Access to Document

10.1145/2933575.2934567

Conference presentation at LICS 2016 (New York, NY, USA)
Lempiäinen, T. (Speaker)
5 Jul 2016 → 9 Jul 2016
Activity: Talk or presentation types › Conference presentation

Cite this

@inproceedings{c11ad500228d4985b35917e390365d80,

title = "Ability to count messages is worth Θ(Δ) rounds in distributed computing",

abstract = "Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing – one of which is the port-numbering model – and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2Δ–2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Δ lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.",

keywords = "distributed computing, port-numbering model, local algorithms, lower bounds, bisimulation",

author = "Tuomo Lempi{\"a}inen",

year = "2016",

month = jul,

day = "5",

doi = "10.1145/2933575.2934567",

language = "English",

series = "Annual ACM/IEEE Symposium on Logic in Computer Science",

publisher = "ACM",

pages = "357--366",

booktitle = "Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science",

address = "United States",

note = "Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ; Conference date: 05-07-2016 Through 08-07-2016",

}

Lempiäinen, T 2016, Ability to count messages is worth Θ(Δ) rounds in distributed computing. in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. Annual ACM/IEEE Symposium on Logic in Computer Science, ACM, New York, NY, USA, pp. 357-366, Annual ACM/IEEE Symposium on Logic in Computer Science, New York, New York, United States, 05/07/2016. https://doi.org/10.1145/2933575.2934567

Ability to count messages is worth Θ(Δ) rounds in distributed computing. / Lempiäinen, Tuomo.
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. New York, NY, USA: ACM, 2016. p. 357-366 (Annual ACM/IEEE Symposium on Logic in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Ability to count messages is worth Θ(Δ) rounds in distributed computing

AU - Lempiäinen, Tuomo

N1 - Conference code: 31

PY - 2016/7/5

Y1 - 2016/7/5

N2 - Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing – one of which is the port-numbering model – and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2Δ–2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Δ lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.

AB - Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing – one of which is the port-numbering model – and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2Δ–2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Δ lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.

KW - distributed computing

KW - port-numbering model

KW - local algorithms

KW - lower bounds

KW - bisimulation

U2 - 10.1145/2933575.2934567

DO - 10.1145/2933575.2934567

M3 - Conference article in proceedings

T3 - Annual ACM/IEEE Symposium on Logic in Computer Science

SP - 357

EP - 366

BT - Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science

PB - ACM

CY - New York, NY, USA

T2 - Annual ACM/IEEE Symposium on Logic in Computer Science

Y2 - 5 July 2016 through 8 July 2016

ER -

Ability to count messages is worth Θ(Δ) rounds in distributed computing

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Activities

Conference presentation at LICS 2016 (New York, NY, USA)

Cite this