Sven Köhler
I'm now a post-doc of Boaz Patt-Shamir at Tel Aviv University. Also see my profile at Google Scholar
Publications
Sven Köhler and Volker Turau. A Distributed Algorithm for Minimum Distance-k Domination in Trees. Journal of Graph Algorithms and Applications, 19(1):223–242, March 2015.
@Article{Telematik_jgaa_2015,
author = {Sven K{\"o}hler and Volker Turau},
title = {A Distributed Algorithm for Minimum Distance-k Domination in Trees},
pages = {223-242},
journal = {Journal of Graph Algorithms and Applications},
volume = {19},
number = {1},
month = mar,
year = 2015,
}
Abstract:
While efficient algorithms for finding minimal distance-k dominating sets exist, finding minimum such sets is NP-hard even for bipartite graphs. This paper presents a distributed algorithm to determine a minimum (connected) distance-k dominating set and a maximum distance-2k independent set of a tree T. It terminates in O(height(T)) rounds and uses O(logk) space. To the best of our knowledge this is the first distributed algorithm that computes a minimum (as opposed to a minimal) distance-k dominating set for trees. The algorithm can also be applied to general graphs, albeit the distance-k dominating sets are not necessarily minimal.
Sven Köhler and Volker Turau. Self-stabilizing local k-placement of replicas with local minimum variance. Theoretical Computer Science, 591:15–27, 2015.
@Article{Telematik_theoretical_computer_science_2015,
author = {Sven K{\"o}hler and Volker Turau},
title = {Self-stabilizing local k-placement of replicas with local minimum variance},
pages = {15-27},
journal = {Theoretical Computer Science},
volume = {591},
year = 2015,
}
Abstract:
Large scale distributed systems require replication of resources to amplify availability and to provide fault tolerance. The placement of replicated resources significantly impacts performance. This paper considers local k-placements: Each node of a network has to place k replicas of a resource among its direct neighbours. The load of a node in a given local k-placement is the number of replicas it stores. The local k-placement problem is to achieve a preferably homogeneous distribution of the loads. We present a novel self-stabilizing, distributed, asynchronous, scalable algorithm for the k-placement problem such that the standard deviation of the distribution of the loads assumes a local minimum.
Sven Köhler. Scalable Fault-Containing Self-Stabilization in Dynamic Networks. PhD Thesis, Hamburg University of Technology, Hamburg, Germany, 2014.
@PhdThesis{Telematik_Köhler_2013_Diss,
author = {Sven K{\"o}hler},
title = {Scalable Fault-Containing Self-Stabilization in Dynamic Networks},
publisher = {Cuvillier Verlag, G{\"o}ttingen, Germany},
school = {Hamburg University of Technology},
address = {Hamburg, Germany},
edition = {1st},
year = 2014,
isbn = {978-3-95404-782-6},
}
Abstract:
Self-stabilizing distributed systems provide a high degree of non-marking fault-tolerance. They recover from transient faults of any scale or nature without human intervention. In general, however, the time needed to recover from small-scale transient faults may not differ significantly from the time needed to recover from large-scale transient faults. Bounding the impact of small-scale faults has been pursued with two independent objectives: reducing the time needed to recover from state corruptions, e.g., fault-containment, and optimizing the system’s reaction upon topological changes, e.g., super-stabilization. The objective of fault-containing self-stabilization is to limit the effects of the corruption of a single node’s state to a local area, i.e., to contain the fault, and to ensure that correctness of the output is regained within constant time. Transformations that add the property of fault-containment to any silent self-stabilizing algorithm exist. However, their fault-gap, i.e., the time needed to prepare for the containment of another fault, is linear in the number of nodes. Hence, these transformations do not perform well in large networks. The root cause of this is the use of global synchronization and reset. This thesis presents a novel scheme for local synchronization. Based on it, a new transformation for adding fault-containment to silent self-stabilizing algorithms is developed. Its fault-gap and slowdown are constant. These are major improvements over previous solutions. The effects of a state corruption are strictly limited to the 2-hop neighborhood of the fault. Similar to previous work, the transformation creates backups of a node’s local state to detect and revert state corruptions. However, the number of backups per node is reduced from O(∆) to 2 backups per node. In order to balance the number of backups stored by each node, this thesis presents a self-stabilizing algorithm for computing a placement of backups such that the standard deviation of the number of backups stored per node assumes a local minimum. Super-stabilizing algorithms are not only self-stabilizing, but also guarantee that a safety property is satisfied while the system recovers from a topology change. This thesis introduces the notion of fault-containing super-stabilization and presents a transformation that can be used to add fault-containment to any silent super-stabilizing algorithm. Fault-containing super-stabilizing distributed algorithms are fault-containing, super-stabilizing, and guarantee that the safety property is satisfied within constant time even if a corruption of a single node’s state and a topology change occur at the same time. The transformations and algorithms presented in this thesis all work under the most general model used in self-stabilization research: the unfair distributed scheduler. Their correctness is proven using a new technique called serialization introduced in this thesis. It is based on the observation that it is possible to replace the parallel execution of a distributed algorithm with a sequential execution, provided the algorithm satisfies a particular condition.
The complete list of publications is available separately.