---
_id: '22283'
abstract:
- lang: eng
text: " We show how to construct an overlay network of constant degree and diameter
$O(\\log n)$ in time $O(\\log n)$ starting from an arbitrary weakly connected
graph.\r\n We assume a synchronous communication network in which nodes can
send messages to nodes they know the identifier of and establish new connections
by sending node identifiers.\r\n If the initial network's graph is weakly connected
and has constant degree, then our algorithm constructs the desired topology with
each node sending and receiving only $O(\\log n)$ messages in each round in time
$O(\\log n)$, w.h.p., which beats the currently best $O(\\log^{3/2} n)$ time algorithm
of [Götte et al., SIROCCO'19].\r\n Since the problem cannot be solved faster
than by using pointer jumping for $O(\\log n)$ rounds (which would even require
each node to communicate $\\Omega(n)$ bits), our algorithm is asymptotically optimal.\r\n
\ We achieve this speedup by using short random walks to repeatedly establish
random connections between the nodes that quickly reduce the conductance of the
graph using an observation of [Kwok and Lau, APPROX'14].\r\n \r\n Additionally,
we show how our algorithm can be used to efficiently solve graph problems in \\emph{hybrid
networks} [Augustine et al., SODA'20].\r\n Motivated by the idea that nodes
possess two different modes of communication, we assume that communication of
the \\emph{initial} edges is unrestricted. In contrast, only polylogarithmically
many messages can be communicated over edges that have been established throughout
an algorithm's execution.\r\n For an (undirected) graph $G$ with arbitrary
degree, we show how to compute connected components, a spanning tree, and biconnected
components in time $O(\\log n)$, w.h.p.\r\n Furthermore, we show how to compute
an MIS in time $O(\\log d + \\log \\log n)$, w.h.p., where $d$ is the initial
degree of $G$."
accept: '1'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Kristian
full_name: Hinnenthal, Kristian
id: '32229'
last_name: Hinnenthal
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Götte T, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction
of Overlays. In: Censor-Hillel K, ed. *Proc. of the 40th ACM Symposium on Principles
of Distributed Computing (PODC ’21)*. New York: ACM. doi:10.1145/3465084.3467932'
apa: 'Götte, T., Hinnenthal, K., Scheideler, C., & Werthmann, J. (n.d.). Time-Optimal
Construction of Overlays. In K. Censor-Hillel (Ed.), *Proc. of the 40th ACM
Symposium on Principles of Distributed Computing (PODC ’21)*. New York: ACM.
https://doi.org/10.1145/3465084.3467932'
bibtex: '@inproceedings{Götte_Hinnenthal_Scheideler_Werthmann, place={New York},
title={Time-Optimal Construction of Overlays}, DOI={10.1145/3465084.3467932},
booktitle={Proc. of the 40th ACM Symposium on Principles of Distributed Computing
(PODC ’21)}, publisher={ACM}, author={Götte, Thorsten and Hinnenthal, Kristian
and Scheideler, Christian and Werthmann, Julian}, editor={Censor-Hillel, KerenEditor}
}'
chicago: 'Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian
Werthmann. “Time-Optimal Construction of Overlays.” In *Proc. of the 40th ACM
Symposium on Principles of Distributed Computing (PODC ’21)*, edited by Keren
Censor-Hillel. New York: ACM, n.d. https://doi.org/10.1145/3465084.3467932.'
ieee: T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction
of Overlays,” in *Proc. of the 40th ACM Symposium on Principles of Distributed
Computing (PODC ’21)*, Virtual.
mla: Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” *Proc. of
the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)*,
edited by Keren Censor-Hillel, ACM, doi:10.1145/3465084.3467932.
short: 'T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, in: K. Censor-Hillel
(Ed.), Proc. of the 40th ACM Symposium on Principles of Distributed Computing
(PODC ’21), ACM, New York, n.d.'
conference:
end_date: 2021-07-30
location: Virtual
name: ACM Symposium on Principles of Distributed Computing (PODC)
start_date: 2021-07-26
date_created: 2021-06-06T19:10:26Z
date_updated: 2021-06-08T13:59:21Z
ddc:
- '000'
department:
- _id: '34'
doi: 10.1145/3465084.3467932
editor:
- first_name: Keren
full_name: Censor-Hillel, Keren
last_name: Censor-Hillel
file:
- access_level: closed
content_type: application/pdf
creator: thgoette
date_created: 2021-06-06T19:12:49Z
date_updated: 2021-06-06T19:12:49Z
file_id: '22284'
file_name: Wicked_Fast_Overlay_Construction(1).pdf
file_size: 590875
relation: main_file
success: 1
file_date_updated: 2021-06-06T19:12:49Z
language:
- iso: eng
place: New York
project:
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '4'
name: SFB 901 - Project Area C
- _id: '13'
name: SFB 901 - Subproject C1
publication: Proc. of the 40th ACM Symposium on Principles of Distributed Computing
(PODC '21)
publication_status: accepted
publisher: ACM
status: public
title: Time-Optimal Construction of Overlays
type: conference
user_id: '34727'
year: '2021'
...
---
_id: '21084'
author:
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: Werthmann J. *Derandomization and Local Graph Problems in the Node-Capacitated
Clique*.; 2021.
apa: Werthmann, J. (2021). *Derandomization and Local Graph Problems in the Node-Capacitated
Clique*.
bibtex: '@book{Werthmann_2021, title={Derandomization and Local Graph Problems in
the Node-Capacitated Clique}, author={Werthmann, Julian}, year={2021} }'
chicago: Werthmann, Julian. *Derandomization and Local Graph Problems in the Node-Capacitated
Clique*, 2021.
ieee: J. Werthmann, *Derandomization and Local Graph Problems in the Node-Capacitated
Clique*. 2021.
mla: Werthmann, Julian. *Derandomization and Local Graph Problems in the Node-Capacitated
Clique*. 2021.
short: J. Werthmann, Derandomization and Local Graph Problems in the Node-Capacitated
Clique, 2021.
date_created: 2021-01-26T13:58:14Z
date_updated: 2021-02-02T07:06:43Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
title: Derandomization and Local Graph Problems in the Node-Capacitated Clique
type: mastersthesis
user_id: '15504'
year: '2021'
...