| |
Records |
Links |
|
Author |
Becker, F.; Montealecre, P.; Rapaport, I.; Todinca, I. |
|
| |
Title |
The Impact Of Locality In The Broadcast Congested Clique Model |
Type |
|
| |
Year |
2020 |
Publication |
Siam Journal On Discrete Mathematics |
Abbreviated Journal |
SIAM Discret. Math. |
|
| |
Volume |
34 |
Issue |
1 |
Pages |
682-700 |
|
| |
Keywords |
broadcast congested clique; induced cycles; graph degeneracy |
|
| |
Abstract |
The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = O(d . log n). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQuE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE <= k) and the problem of detecting an induced cycle of length at least k +1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = left perpendicular k/2 right perpendicular + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = left perpendicular k/3 right perpendicular, then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Omega(n/ log n). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE <= k with bandwitdh b = O(n(1/left perpendicular k/2 right perpendicular). log n). On the negative side, we prove that, if epsilon <= 1/3 and 0 < r <= k/4, then any epsilon-error, R-round, b-bandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE(<= k )satisfies R . b = Omega(n(1/left perpendicular k/2 right perpendicular)). |
|
| |
Address |
[Becker, F.; Todinca, I] Univ Orleans, INSA Ctr Val Loire, LIFO EA 4022, Orleans, France, Email: florent.becker@univ-orleans.fr; |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Siam Publications |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0895-4801 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000546886700033 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
1182 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Becker, F.; Montealegre, P.; Rapaport, I.; Todinca, I. |
|
| |
Title |
The role of randomness in the broadcast congested clique model |
Type |
|
| |
Year |
2021 |
Publication |
Information and Computation |
Abbreviated Journal |
Inf. Comput. |
|
| |
Volume |
281 |
Issue |
|
Pages |
104669 |
|
| |
Keywords |
Distributed computing; Broadcast congested clique; Message size complexity; Private and public coins; Simultaneous multi-party communication |
|
| |
Abstract |
We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.
This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:
If more than one round is allowed, public randomness is as powerful as private ran-domness.
One-round public-coin algorithms can be exponentially more powerful than determin-istic algorithms running in several rounds.
One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms.
One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
|
Place of Publication |
|
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0890-5401 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000721215200042 |
Approved |
|
|
| |
Call Number |
UAI @ alexi.delcanto @ |
Serial |
1491 |
|
| Permanent link to this record |
