5 papers
On the Complexity of Local Graph Transformations
Christian Scheideler, Alexander Setzer
We consider the problem of transforming a given graph into a desired graph by applying a minimum number primitives from a particular set of local graph transformation p…
Relays: A New Approach for the Finite Departure Problem in Overlay Networks
Christian Scheideler, Alexander Setzer
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 co…
On Underlay-Aware Self-Stabilizing Overlay Networks
Thorsten Götte, Christian Scheideler, Alexander Setzer
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 o…
Breaking the Barrier: Fast Consensus under a Late Adversary
Peter Robinson, Christian Scheideler, Alexander Setzer
We study the consensus problem in a synchronous distributed system of nodes under an adaptive adversary that has a slightly outdated view of the system and can block all incomi…
Skueue: A Scalable and Sequentially Consistent Distributed Queue
Michael Feldmann, Christian Scheideler, Alexander Setzer
We propose a distributed protocol for a queue, called \textsc{Skueue}, which spreads its data fairly onto multiple processes, avoiding bottlenecks in high throughput scenarios. \te…