TY - CONF
AB - We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 10586
KW - Graphs transformations
KW - NP-hardness
KW - approximation algorithms
TI - On the Complexity of Local Graph Transformations
VL - 132
ER -
TY - CONF
AB - 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.
AU - Robinson, Peter
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 3422
KW - distributed consensus
KW - randomized algorithm
KW - adaptive adversary
KW - complexity lower bound
SN - 978-1-4503-5799-9/18/07
T2 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary
ER -
TY - CONF
AB - We present a self-stabilizing protocol for an overlay network that constructs the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted tree. The weight of an overlay edge between two nodes is the weighted length of their shortest path in the tree. We rigorously prove that our protocol works correctly under asynchronous and non-FIFO message delivery. Further, the protocol stabilizes after O(N^2) asynchronous rounds where N is the number of nodes in the overlay.
AU - Götte, Thorsten
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 5222
T2 - Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)
TI - On Underlay-Aware Self-Stabilizing Overlay Networks
VL - 11201
ER -
TY - CONF
AB - We present a peer-to-peer network that supports the efficient processing of orthogonal range queries $R=\bigtimes_{i=1}^{d}[a_i,\,b_i]$ in a $d$-dimensional point space.\\
The network is the same for each dimension, namely a distance halving network like the one introduced by Naor and Wieder (ACM TALG'07).
We show how to execute such range queries using $\mathcal{O}\left(2^{d'}d\,\log m + d\,|R|\right)$ hops (and the same number of messages) in total. Here $[m]^d$ is the ground set, $|R|$ is the size and $d'$ the dimension of the queried range.
Furthermore, if the peers form a distributed network, the query can be answered in $\mathcal{O}\left(d\,\log m + d\,\sum_{i=1}^{d}(b_i-a_i+1)\right)$ communication rounds.
Our algorithms are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers.
AU - Benter, Markus
AU - Knollmann, Till
AU - Meyer auf der Heide, Friedhelm
AU - Setzer, Alexander
AU - Sundermeier, Jannik
ID - 4375
KW - Distributed Storage
KW - Multi-Dimensional Range Queries
KW - Peer-to-Peer
KW - Hilbert Curve
T2 - Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)
TI - A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension
ER -
TY - CONF
AB - A fundamental problem for overlay networks is to safely exclude leaving nodes, i.e., the nodes requesting to leave the overlay network are excluded from it without affecting its connectivity. To rigorously study self-stabilizing solutions to this problem, the Finite Departure Problem (FDP) has been proposed [9]. In the FDP we are given a network of processes in an arbitrary state, and the goal is to eventually arrive at (and stay in) a state in which all leaving processes irrevocably decided to leave the system while for all weakly-connected components in the initial overlay network, all staying processes in that component will still form a weakly connected component. In the standard interconnection model, the FDP is known to be unsolvable by local control protocols, so oracles have been investigated that allow the problem to be solved [9]. To avoid the use of oracles, we introduce a new interconnection model based on relays. Despite the relay model appearing to be rather restrictive, we show that it is universal, i.e., it is possible to transform any weakly-connected topology into any other weakly-connected topology, which is important for being a useful interconnection model for overlay networks. Apart from this, our model allows processes to grant and revoke access rights, which is why we believe it to be of interest beyond the scope of this paper. We show how to implement the relay layer in a self-stabilizing way and identify properties protocols need to satisfy so that the relay layer can recover while serving protocol requests.
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 5216
T2 - Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)
TI - Relays: A New Approach for the Finite Departure Problem in Overlay Networks
ER -
TY - CONF
AB - 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.
AU - Feldmann, Michael
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 1164
T2 - Proceedings of the 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)
TI - Skueue: A Scalable and Sequentially Consistent Distributed Queue
ER -
TY - GEN
AB - In this paper, we investigate the use of trusted execution environments (TEEs, such as Intel's SGX) for an anonymous communication infrastructure over untrusted networks.
For this, we present the general idea of exploiting trusted execution environments for the purpose of anonymous communication, including a continuous-time security framework that models strong anonymity guarantees in the presence of an adversary that observes all network traffic and can adaptively corrupt a constant fraction of participating nodes.
In our framework, a participating node can generate a number of unlinkable pseudonyms. Messages are sent from and to pseudonyms, allowing both senders and receivers of messages to remain anonymous. We introduce a concrete construction, which shows viability of our TEE-based approach to anonymous communication. The construction draws from techniques from cryptography and overlay networks.
Our techniques are very general and can be used as a basis for future constructions with similar goals.
AU - Blömer, Johannes
AU - Bobolz, Jan
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 5820
TI - Provably Anonymous Communication Based on Trusted Execution Environments
ER -
TY - CONF
AB - For overlay networks, the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network. We investigate overlay networks that are not only self-stabilizing but that also ensure that monotonic searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. Monotonic searchability was recently introduced in OPODIS 2015, in which the authors provide a solution for a simple line topology.We present the first universal approach to maintain monotonic searchability that is applicable to a wide range of topologies. As the base for our approach, we introduce a set of primitives for manipulating overlay networks that allows us to maintain searchability and show how existing protocols can be transformed to use theses primitives.We complement this result with a generic search protocol that together with the use of our primitives guarantees monotonic searchability.As an additional feature, searching existing nodes with the generic search protocol is as fast as searching a node with any other fixed routing protocol once the topology has stabilized.
AU - Scheideler, Christian
AU - Setzer, Alexander
AU - Strothmann, Thim Frederik
ID - 142
T2 - Proceedings of the 30th International Symposium on Distributed Computing (DISC)
TI - Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks
ER -
TY - CONF
AB - Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et. al (SSS 2014). This makes our protocol even capable of handling node dynamics.
AU - Scheideler, Christian
AU - Setzer, Alexander
AU - Strothmann, Thim Frederik
ID - 241
T2 - Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)
TI - Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures
ER -
TY - CONF
AB - In this work we present the first distributed storage system that is provably robust against crash failures issued by an adaptive adversary, i.e., for each batch of requests the adversary can decide based on the entire system state which servers will be unavailable for that batch of requests. Despite up to \gamma n^{1/\log\log n} crashed servers, with \gamma>0 constant and n denoting the number of servers, our system can correctly process any batch of lookup and write requests (with at most a polylogarithmic number of requests issued at each non-crashed server) in at most a polylogarithmic number of communication rounds, with at most polylogarithmic time and work at each server and only a logarithmic storage overhead. Our system is based on previous work by Eikel and Scheideler (SPAA 2013), who presented IRIS, a distributed information system that is provably robust against the same kind of crash failures. However, IRIS is only able to serve lookup requests. Handling both lookup and write requests has turned out to require major changes in the design of IRIS.
AU - Scheideler, Christian
AU - Setzer, Alexander
AU - Eikel, Martina
ID - 371
T2 - Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS)
TI - RoBuSt: A Crash-Failure-Resistant Distributed Storage System
ER -
TY - CONF
AB - We present a factor $14D^2$ approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where $D$ is the maximum degree in the graph. Given a suitable decomposition of the graph, our algorithm runs in time $O(|E|)$ and is very easy to implement. Its divide-and-conquer approach allows for an effective parallelization. Note that a suitable decomposition can also be computed in time $O(|E|\log{|E|})$ (or even $O(\log{|E|}\log^*{|E|})$ on an EREW PRAM using $O(|E|)$ processors). For the proof of the approximation ratio, we use a sophisticated charging method that uses techniques similar to amortized analysis in advanced data structures. On general graphs, the minimum linear arrangement problem is known to be NP-hard. To the best of our knowledge, the minimum linear arrangement problem on series-parallel graphs has not been studied before.
AU - Scheideler, Christian
AU - Eikel, Martina
AU - Setzer, Alexander
ID - 397
T2 - Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)
TI - Minimum Linear Arrangement of Series-Parallel Graphs
ER -
TY - GEN
AU - Setzer, Alexander
ID - 555
TI - Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs
ER -
TY - CONF
AB - Network creation games model the creation and usage costs of networks formed by a set of selfish peers.Each peer has the ability to change the network in a limited way, e.g., by creating or deleting incident links.In doing so, a peer can reduce its individual communication cost.Typically, these costs are modeled by the maximum or average distance in the network.We introduce a generalized version of the basic network creation game (BNCG).In the BNCG (by Alon et al., SPAA 2010), each peer may replace one of its incident links by a link to an arbitrary peer.This is done in a selfish way in order to minimize either the maximum or average distance to all other peers.That is, each peer works towards a network structure that allows himself to communicate efficiently with all other peers.However, participants of large networks are seldom interested in all peers.Rather, they want to communicate efficiently with a small subset only.Our model incorporates these (communication) interests explicitly.Given peers with interests and a communication network forming a tree, we prove several results on the structure and quality of equilibria in our model.We focus on the MAX-version, i.e., each node tries to minimize the maximum distance to nodes it is interested in, and give an upper bound of O(\sqrt(n)) for the private costs in an equilibrium of n peers.Moreover, we give an equilibrium for a circular interest graph where a node has private cost Omega(\sqrt(n)), showing that our bound is tight.This example can be extended such that we get a tight bound of Theta(\sqrt(n)) for the price of anarchy.For the case of general networks we show the price of anarchy to be Theta(n).Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers.
AU - Cord-Landwehr, Andreas
AU - Huellmann (married name: Eikel), Martina
AU - Kling, Peter
AU - Setzer, Alexander
ID - 628
T2 - Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)
TI - Basic Network Creation Games with Communication Interests
ER -