Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?

Peter Robinson

doi:10.1145/3583668.3594575

Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?

Peter Robinson

Computer & Cyber Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of ω(log3 n) bits in the worst case. Consequently, computing an MST under the standard assumption of O(log n)-size messages requires at least 2 rounds. This is the first round complexity lower bound in the unicast congested clique for a problem where the output size is small, i.e., O(n log n) bits. Our lower bound holds as long as every edge of the MST is output by an incident node. To the best of our knowledge, all prior lower bounds for the unicast congested clique either considered problems with large output sizes (e.g., subgraph enumeration) or required every node to learn the entire output.

Original language	English (US)
Title of host publication	PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	168-171
Number of pages	4
ISBN (Electronic)	9798400701214
DOIs	https://doi.org/10.1145/3583668.3594575
State	Published - Jun 19 2023
Event	42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023 - Orlando, United States Duration: Jun 19 2023 → Jun 23 2023

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference	42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023
Country/Territory	United States
City	Orlando
Period	6/19/23 → 6/23/23

Keywords

congested clique
distributed graph algorithm
lower bound

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/3583668.3594575

Cite this

Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? / Robinson, Peter.
PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2023. p. 168-171 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Robinson, P 2023, Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? in PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 168-171, 42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023, Orlando, United States, 6/19/23. https://doi.org/10.1145/3583668.3594575

@inproceedings{c359f6447209433bb12f8b9d1f0d2440,

title = "Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?",

abstract = "We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of ω(log3 n) bits in the worst case. Consequently, computing an MST under the standard assumption of O(log n)-size messages requires at least 2 rounds. This is the first round complexity lower bound in the unicast congested clique for a problem where the output size is small, i.e., O(n log n) bits. Our lower bound holds as long as every edge of the MST is output by an incident node. To the best of our knowledge, all prior lower bounds for the unicast congested clique either considered problems with large output sizes (e.g., subgraph enumeration) or required every node to learn the entire output.",

keywords = "congested clique, distributed graph algorithm, lower bound",

author = "Peter Robinson",

note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023 ; Conference date: 19-06-2023 Through 23-06-2023",

year = "2023",

month = jun,

day = "19",

doi = "10.1145/3583668.3594575",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "168--171",

booktitle = "PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing",

}

TY - GEN

T1 - Brief Announcement

T2 - 42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023

AU - Robinson, Peter

PY - 2023/6/19

Y1 - 2023/6/19

N2 - We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of ω(log3 n) bits in the worst case. Consequently, computing an MST under the standard assumption of O(log n)-size messages requires at least 2 rounds. This is the first round complexity lower bound in the unicast congested clique for a problem where the output size is small, i.e., O(n log n) bits. Our lower bound holds as long as every edge of the MST is output by an incident node. To the best of our knowledge, all prior lower bounds for the unicast congested clique either considered problems with large output sizes (e.g., subgraph enumeration) or required every node to learn the entire output.

AB - We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of ω(log3 n) bits in the worst case. Consequently, computing an MST under the standard assumption of O(log n)-size messages requires at least 2 rounds. This is the first round complexity lower bound in the unicast congested clique for a problem where the output size is small, i.e., O(n log n) bits. Our lower bound holds as long as every edge of the MST is output by an incident node. To the best of our knowledge, all prior lower bounds for the unicast congested clique either considered problems with large output sizes (e.g., subgraph enumeration) or required every node to learn the entire output.

KW - congested clique

KW - distributed graph algorithm

KW - lower bound

UR - http://www.scopus.com/inward/record.url?scp=85163929520&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163929520&partnerID=8YFLogxK

U2 - 10.1145/3583668.3594575

DO - 10.1145/3583668.3594575

M3 - Conference contribution

AN - SCOPUS:85163929520

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 168

EP - 171

BT - PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

Y2 - 19 June 2023 through 23 June 2023

ER -

Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this