Search Results

Documents authored by Elsässer, Robert

Document
DOI: 10.4230/LIPIcs.DISC.2021.9
Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion

Authors: Gregor Bankhamer, Robert Elsässer, and Stefan Schmid

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
To ensure high availability, datacenter networks must rely on local fast rerouting mechanisms that allow routers to quickly react to link failures, in a fully decentralized manner. However, configuring these mechanisms to provide a high resilience against multiple failures while avoiding congestion along failover routes is algorithmically challenging, as the rerouting rules can only depend on local failure information and must be defined ahead of time. This paper presents a randomized local fast rerouting algorithm for Clos networks, the predominant datacenter topologies. Given a graph G = (V,E) describing a Clos topology, our algorithm defines local routing rules for each node v ∈ V, which only depend on the packet’s destination and are conditioned on the incident link failures. We prove that as long as number of failures at each node does not exceed a certain bound, our algorithm achieves an asymptotically minimal congestion up to polyloglog factors along failover paths. Our lower bounds are developed under some natural routing assumptions.
Cite as

Gregor Bankhamer, Robert Elsässer, and Stefan Schmid. Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bankhamer_et_al:LIPIcs.DISC.2021.9,
  author =	{Bankhamer, Gregor and Els\"{a}sser, Robert and Schmid, Stefan},
  title =	{{Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.9},
  URN =		{urn:nbn:de:0030-drops-148117},
  doi =		{10.4230/LIPIcs.DISC.2021.9},
  annote =	{Keywords: local failover routing, congestion, randomized algorithms, datacenter networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.10
A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States

Authors: Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired output property. The main performance objectives in designing such protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem, which uses Theta(log n) states (per agent) and stabilizes in O(log^{5/3} n) parallel time (i.e., in O(n log^{5/3} n) interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that exact-majority protocols which stabilize in expected O(n^{1-Omega(1)}) parallel time and have the properties of monotonicity and output dominance require Omega(log n) states. Note that the properties mentioned above are satisfied by all known population protocols for exact majority, including ours. They also showed an O(log^2 n)-time exact-majority protocol with O(log n) states, which, prior to our work, was the fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on O(log n) phases and requires that all agents are well synchronized within each phase, leading naturally to upper bounds of the order of log^2 n because of Theta(log n) synchronization time per phase. We show how this framework can be tightened with weak synchronization to break the O(log^2 n) upper bound of previous protocols.
Cite as

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.DISC.2018.10,
  author =	{Berenbrink, Petra and Els\"{a}sser, Robert and Friedetzky, Tom and Kaaser, Dominik and Kling, Peter and Radzik, Tomasz},
  title =	{{A Population Protocol for Exact Majority with O(log5/3 n)  Stabilization Time and Theta(log n) States}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.10},
  URN =		{urn:nbn:de:0030-drops-97999},
  doi =		{10.4230/LIPIcs.DISC.2018.10},
  annote =	{Keywords: Population Protocols, Randomized Algorithms, Majority}
}
Document
DOI: 10.4230/DagRep.3.1.94
Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl Seminar 13042)

Authors: Benjamin Doerr, Robert Elsässer, and Pierre Fraigniaud

Published in: Dagstuhl Reports, Volume 3, Issue 1 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13042 "Epidemic Algorithms and Processes: From Theory to Applications", which took place from January 20 to 25, 2013 at Schloss Dagstuhl - Leibniz Center for Informatics. Several research topics were covered by the seminar participants, including scientists working in Theoretical Computer Science, as well as researchers from the more practical area of Computer Systems. Most of the participants presented their recent results on the topic of the seminar, as well as some challenging new directions and open problems. The presentations contained a description of the main research area for a wide audience. During the seminar, ample time was reserved for informal discussions between participants working on different topics. In our executive summary, we describe the main field of the seminar, as well as our goals in general. Then, we present the abstracts of the presentations given during the seminar.
Cite as

Benjamin Doerr, Robert Elsässer, and Pierre Fraigniaud. Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl Seminar 13042). In Dagstuhl Reports, Volume 3, Issue 1, pp. 94-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{doerr_et_al:DagRep.3.1.94,
  author =	{Doerr, Benjamin and Els\"{a}sser, Robert and Fraigniaud, Pierre},
  title =	{{Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl Seminar 13042)}},
  pages =	{94--110},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{1},
  editor =	{Doerr, Benjamin and Els\"{a}sser, Robert and Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.1.94},
  URN =		{urn:nbn:de:0030-drops-40104},
  doi =		{10.4230/DagRep.3.1.94},
  annote =	{Keywords: Message dissemination, Epidemic spreading, Dynamic spreading processes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1842
Cover Time and Broadcast Time

Authors: Robert Elsässer and Thomas Sauerwald

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that ``the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. In more detail, our results are as follows: \begin{itemize} \item For any graph $G=(V,E)$ of size $n$ and minimum degree $\delta$, we have $\mathcal{R}(G)= \mathcal{O}(\frac{|E|}{\delta} \cdot \log n)$, where $\mathcal{R}(G)$ denotes the quotient of the cover time and broadcast time. This bound is tight for binary trees and tight up to logarithmic factors for many graphs including hypercubes, expanders and lollipop graphs. \item For any $\delta$-regular (or almost $\delta$-regular) graph $G$ it holds that $\mathcal{R}(G) = \Omega(\frac{\delta^2}{n} \cdot \frac{1}{\log n})$. Together with our upper bound on $\mathcal{R}(G)$, this lower bound strongly confirms the intuition of Chandra et al.~for graphs with minimum degree $\Theta(n)$, since then the cover time equals the broadcast time multiplied by $n$ (neglecting logarithmic factors). \item Conversely, for any $\delta$ we construct almost $\delta$-regular graphs that satisfy $\mathcal{R}(G) = \mathcal{O}(\max \{ \sqrt{n},\delta \} \cdot \log^2 n)$. Since any regular expander satisfies $\mathcal{R}(G) = \Theta(n)$, the strong relationship given above does not hold if $\delta$ is polynomially smaller than $n$. \end{itemize} Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap).
Cite as

Robert Elsässer and Thomas Sauerwald. Cover Time and Broadcast Time. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 373-384, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{elsasser_et_al:LIPIcs.STACS.2009.1842,
  author =	{Els\"{a}sser, Robert and Sauerwald, Thomas},
  title =	{{Cover Time and Broadcast Time}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{373--384},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1842},
  URN =		{urn:nbn:de:0030-drops-18421},
  doi =		{10.4230/LIPIcs.STACS.2009.1842},
  annote =	{Keywords: Random walk, Randomized algorithms, Parallel and distributed algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact