@inproceedings{12944,
author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian}},
booktitle = {{Structural Information and Communication Complexity}},
title = {{{Faster Construction of Overlay Networks}}},
doi = {{10.1007/978-3-030-24922-9_18}},
year = {{2019}},
}
@inproceedings{15627,
author = {{Augustine, John and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp}},
booktitle = {{Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms}},
isbn = {{9781611975994}},
pages = {{1280--1299}},
title = {{{Shortest Paths in a Hybrid Network Model}}},
doi = {{10.1137/1.9781611975994.78}},
year = {{2019}},
}
@article{14830,
author = {{Gmyr, Robert and Lefevre, Jonas and Scheideler, Christian}},
journal = {{Theory Comput. Syst.}},
number = {{2}},
pages = {{177--199}},
title = {{{Self-Stabilizing Metric Graphs}}},
doi = {{10.1007/s00224-017-9823-4}},
volume = {{63}},
year = {{2019}},
}
@inproceedings{14539,
author = {{Castenow, Jannik and Kolb, Christina and Scheideler, Christian}},
booktitle = {{Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO)}},
location = {{L'Aquila, Italy}},
pages = {{345--348}},
title = {{{A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks}}},
doi = {{10.1007/978-3-030-24922-9\_26}},
year = {{2019}},
}
@inproceedings{13182,
abstract = {{We consider congestion control in peer-to-peer distributed systems.
The problem can be reduced to the following scenario: Consider a set $V$ of $n$ peers (called \emph{clients} in this paper) that want to send messages to a fixed common peer (called \emph{server} in this paper).
We assume that each client $v \in V$ sends a message with probability $p(v) \in [0,1)$ and the server has a capacity of $\sigma \in \mathbb{N}$, i.e., it can recieve at most $\sigma$ messages per round and excess messages are dropped.
The server can modify these probabilities when clients send messages.
Ideally, we wish to converge to a state with $\sum p(v) = \sigma$ and $p(v) = p(w)$ for all $v,w \in V$.
We propose a \emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state.
Our protocol lets the system converge from \emph{any} initial state to a state where $\sum p(v) \in \left[\sigma \pm \epsilon\right]$ and $|p(v)-p(w)| \in O(\frac{1}{n})$.
This property is then maintained for $\Omega(n^{\mathfrak{c}})$ rounds in expectation.
In particular, the initial client probabilities and server variables are not necessarily well-defined, i.e., they may have arbitrary values.
Our protocol uses only $O(W + \log n)$ bits of memory where $W$ is length of node identifiers, making it very lightweight.
Finally we state a lower bound on the convergence time an see that our protocol performs asymptotically optimal (up to some polylogarithmic factor).
}},
author = {{Feldmann, Michael and Götte, Thorsten and Scheideler, Christian}},
booktitle = {{Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}},
pages = {{149--164}},
publisher = {{Springer, Cham}},
title = {{{A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory}}},
doi = {{https://doi.org/10.1007/978-3-030-34992-9_13}},
year = {{2019}},
}
@inproceedings{13652,
author = {{Hinnenthal, Kristian and Scheideler, Christian and Struijs, Martijn}},
booktitle = {{33rd International Symposium on Distributed Computing (DISC 2019)}},
title = {{{Fast Distributed Algorithms for LP-Type Problems of Low Dimension}}},
doi = {{10.4230/LIPICS.DISC.2019.23}},
year = {{2019}},
}
@inproceedings{3422,
abstract = {{We study the consensus problem in a synchronous distributed system of n nodes under an adaptive adversary that has a slightly outdated view of the system and can block all incoming and outgoing communication of a constant fraction of the nodes in each round. Motivated by a result of Ben-Or and Bar-Joseph (1998), showing that any consensus algorithm that is resilient against a linear number of crash faults requires $\tilde \Omega(\sqrt n)$ rounds in an n-node network against an adaptive adversary, we consider a late adaptive adversary, who has full knowledge of the network state at the beginning of the previous round and unlimited computational power, but is oblivious to the current state of the nodes.
Our main contributions are randomized distributed algorithms that achieve consensus with high probability among all except a small constant fraction of the nodes (i.e., "almost-everywhere'') against a late adaptive adversary who can block up to ε n$ nodes in each round, for a small constant ε >0$. Our first protocol achieves binary almost-everywhere consensus and also guarantees a decision on the majority input value, thus ensuring plurality consensus. We also present an algorithm that achieves the same time complexity for multi-value consensus. Both of our algorithms succeed in $O(log n)$ rounds with high probability, thus showing an exponential gap to the $\tilde\Omega(\sqrt n)$ lower bound of Ben-Or and Bar-Joseph for strongly adaptive crash-failure adversaries, which can be strengthened to $\Omega(n)$ when allowing the adversary to block nodes instead of permanently crashing them. Our algorithms are scalable to large systems as each node contacts only an (amortized) constant number of peers in each communication round. We show that our algorithms are optimal up to constant (resp.\ sub-logarithmic) factors by proving that every almost-everywhere consensus protocol takes $\Omega(log_d n)$ rounds in the worst case, where d is an upper bound on the number of communication requests initiated per node in each round. We complement our theoretical results with an experimental evaluation of the binary almost-everywhere consensus protocol revealing a short convergence time even against an adversary blocking a large fraction of nodes.}},
author = {{Robinson, Peter and Scheideler, Christian and Setzer, Alexander}},
booktitle = {{Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}},
isbn = {{978-1-4503-5799-9/18/07}},
keywords = {{distributed consensus, randomized algorithm, adaptive adversary, complexity lower bound}},
location = {{Wien}},
title = {{{Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary}}},
doi = {{10.1145/3210377.3210399}},
year = {{2018}},
}
@inproceedings{1163,
abstract = {{In this paper we present two major results:
First, we introduce the first self-stabilizing version of a supervised overlay network (as introduced in~\cite{DBLP:conf/ispan/KothapalliS05}) by presenting a self-stabilizing supervised skip ring.
Secondly, we show how to use the self-stabilizing supervised skip ring to construct an efficient self-stabilizing publish-subscribe system.
That is, in addition to stabilizing the overlay network, every subscriber of a topic will eventually know all of the publications that have been issued so far for that topic. The communication work needed to processes a subscribe or unsubscribe operation is just a constant in a legitimate state, and the communication work of checking whether the system is still in a legitimate state is just a constant on expectation for the supervisor as well as any process in the system.
}},
author = {{Feldmann, Michael and Kolb, Christina and Scheideler, Christian and Strothmann, Thim Frederik}},
booktitle = {{Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)}},
keywords = {{Topological Self-stabilization, Supervised Overlay, Publish-Subscribe System}},
location = {{Vancouver}},
publisher = {{IEEE}},
title = {{{Self-Stabilizing Supervised Publish-Subscribe Systems}}},
doi = {{10.1109/IPDPS.2018.00114}},
year = {{2018}},
}
@inproceedings{1164,
abstract = {{We propose a distributed protocol for a queue, called Skueue, which spreads its data fairly onto multiple processes, avoiding bottlenecks in high throughput scenarios.
Skueuecan be used in highly dynamic environments, through the addition of join and leave requests to the standard queue operations enqueue and dequeue.
Furthermore Skueue satisfies sequential consistency in the asynchronous message passing model.
Scalability is achieved by aggregating multiple requests to a batch, which can then be processed in a distributed fashion without hurting the queue semantics.
Operations in Skueue need a logarithmic number of rounds w.h.p. until they are processed, even under a high rate of incoming requests.}},
author = {{Feldmann, Michael and Scheideler, Christian and Setzer, Alexander}},
booktitle = {{Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)}},
location = {{Vancouver}},
publisher = {{IEEE}},
title = {{{Skueue: A Scalable and Sequentially Consistent Distributed Queue}}},
doi = {{10.1109/IPDPS.2018.00113}},
year = {{2018}},
}
@article{1796,
author = {{J. Daymude, Joshua and Derakhshandeh, Zahra and Gmyr, Robert and Porter, Alexandra and W. Richa, Andrea and Scheideler, Christian and Strothmann, Thim Frederik}},
journal = {{Natural Computing}},
number = {{1}},
pages = {{81----96}},
title = {{{On the runtime of universal coating for programmable matter}}},
doi = {{10.1007/s11047-017-9658-6}},
year = {{2018}},
}