Source author record

Alexander Setzer

Alexander Setzer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Discrete Mathematics Computational Complexity Computer Science and Game Theory Networking and Internet Architecture

Catalog footprint

What is connected

7works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

On the Complexity of Local Graph Transformations

We consider the problem of transforming a given graph $G_s$ into a desired graph $G_t$ by applying a minimum number 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.

preprint2016arXiv

Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks

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.

preprint2015arXiv

RoBuSt: A Crash-Failure-Resistant Distributed Storage System

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 $γn^{1/\log\log n}$ crashed servers, with $γ>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.

preprint2015arXiv

Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures (full version)

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. This is the full version of a correspondent paper published at OPODIS'15.

preprint2014arXiv

Minimum Linear Arrangement of Series-Parallel Graphs

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.

preprint2014arXiv

The planar minimum linear arrangement problem is different from the minimum linear arrangement problem

In various research papers, such as [2], one will find the claim that the minLA is optimally solvable on outerplanar graphs, with a reference to [1]. However, the problem solved in that publication, which we refer to as the planar minimum linear arrangement problem (planar minLA), is different from the minimum linear arrangement problem (minLA), as we show in this article.

preprint2012arXiv

Basic Network Creation Games with Communication Interests

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 only with a small subset of peers. Our model incorporates these (communication) interests explicitly. In the MAX-version, each node tries to minimize its maximum distance to nodes it is interested in. 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. For the MAX-version, we give an upper worst case 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 Ω(\sqrt{n}), showing that our bound is tight. This example can be extended such that we get a tight bound of Θ(\sqrt{n}) for the price of anarchy. For the case of general communication networks we show the price of anarchy to be Θ(n). Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers.