*Journal of Graph Algorithms and Applications*, 19(1):223–242, March 2015.

# Publications

Journal Articles | Conference Contributions | PhD Theses | Students' Theses

Also see my profile at Google Scholar

## Journal Articles

Sven Köhler and Volker Turau. A Distributed Algorithm for Minimum Distance-k Domination in Trees.

@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 and Volker Turau. Fault-containing self-stabilization in asynchronous systems with constant fault-gap.

*Distributed Computing*, 25(3):207–224, 2012.@Article{Telematik_KT_2011_DC,
author = {Sven K{\"o}hler and Volker Turau},
title = {Fault-containing self-stabilization in asynchronous systems with constant fault-gap},
pages = {207-224},
journal = {Distributed Computing},
volume = {25},
number = {3},
year = 2012,
issn = {0178-2770},
}

**Abstract**: This paper presents a new transformation which adds fault-containment properties to silent self-stabilizing algorithms. The transformation features a constant slow-down factor and the fault-gap—that is the minimal time between two containable faults—is also constant. The transformation scales well to arbitrarily large systems and avoids global synchronization. The presented transformation is the first with a constant fault-gap and requires no knowledge of the system size.

## Conference Contributions

Sven Köhler, Volker Turau and Gerhard Mentges. Self-stabilizing local k-placement of replicas with minimal variance. In

*Proceedings of the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'12)*, Springer, October 2012, pp. 16–30. Toronto, Canada.@InProceedings{Telematik_KT_SSS12,
author = {Sven K{\"o}hler and Volker Turau and Gerhard Mentges},
title = {Self-stabilizing local k-placement of replicas with minimal variance},
booktitle = {Proceedings of the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'12)},
pages = {16-30},
series = {Lecture Notes in Computer Science},
volume = {7596},
publisher = {Springer},
day = {1-4},
month = oct,
year = 2012,
location = {Toronto, Canada},
}

**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 neighbors. 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 and Volker Turau. Space-efficient fault-containment in dynamic networks. In

*Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'11)*, Springer, October 2011, pp. 311–325. Grenoble, France.@InProceedings{Telematik_KT_SSS11,
author = {Sven K{\"o}hler and Volker Turau},
title = {Space-efficient fault-containment in dynamic networks},
booktitle = {Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'11)},
pages = {311-325},
series = {Lecture Notes in Computer Science},
volume = {6976},
publisher = {Springer},
day = {10-12},
month = oct,
year = 2011,
location = {Grenoble, France},
}

**Abstract**: Bounding the impact of transient small-scale faults by self-stabilizing protocols has been pursued with independent objectives: Optimizing the system's reaction upon topological changes (e.g. super-stabilization), and reducing system recovery time from memory corruptions (e.g. fault-containment). Even though transformations adding either super-stabilization or fault-containment to existing protocols exists, none of them preserves the other. This paper makes a first attempt to combine both objectives. We provide a transformation adding fault-containment to silent self-stabilizing protocols while simultaneously preserving the property of self-stabilization and the protocol's behavior in face of topological changes. In particular, the protocol's response to a topology change remains unchanged even if a memory corruption occurs in parallel to the topology change. The presented transformation increases the memory footprint only by a factor of 4 and adds O(1) bits per edge. All previously known transformations for fault-containing self-stabilization increase the memory footprint by a factor of 2m/n.

Sven Köhler and Volker Turau. A new Technique for proving Self-Stabilization under the Distributed Scheduler. In

*Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'10)*, Springer, September 2010, pp. 65–79. New York, NY, USA.@InProceedings{Telematik_KT_ProofTechnique,
author = {Sven K{\"o}hler and Volker Turau},
title = {A new Technique for proving Self-Stabilization under the Distributed Scheduler},
booktitle = {Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'10)},
pages = {65-79},
series = {Lecture Notes in Computer Science},
volume = {6366},
publisher = {Springer},
day = {20-22},
month = sep,
year = 2010,
location = {New York, NY, USA},
}

**Abstract**: Proving stabilization of a complex algorithm under the distributed scheduler is a non-trivial task. This paper introduces a new method which allows to extend proofs for the central scheduler to the distributed scheduler. The practicability of the method is shown by applying it to two existing algorithms, for which stabilization under the distributed scheduler was an open problem.

Sven Köhler and Volker Turau. Fault-containing self-stabilization in asynchronous systems with constant fault-gap. In

*Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS'10)*, IEEE Computer Society, June 2010, pp. 418–427. Genoa, Italy.@InProceedings{Telematik_KT_FaultContain,
author = {Sven K{\"o}hler and Volker Turau},
title = {Fault-containing self-stabilization in asynchronous systems with constant fault-gap},
booktitle = {Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS'10)},
pages = {418-427},
publisher = {IEEE Computer Society},
day = {21-25},
month = jun,
year = 2010,
location = {Genoa, Italy},
}

**Abstract**: This paper presents a new transformation which adds fault-containment properties to any silent self-stabilizing protocol. The transformation features a constant slow-down factor and the fault-gap – that is the minimal time between two containable faults – is constant. The transformation scales well to arbitrarily large systems and avoids global synchronization.

Sven Köhler and Martin Ziegler. On the Stability of Fast Polynomial Arithmetic. In

*Proceedings of the 8th Conference on Real Numbers and Computers*, 2008. Santiago de Compostela, Spain.@InProceedings{KOEHLER_RNC08,
author = {Sven K{\"o}hler and Martin Ziegler},
title = {On the Stability of Fast Polynomial Arithmetic},
booktitle = {Proceedings of the 8th Conference on Real Numbers and Computers},
year = 2008,
location = {Santiago de Compostela, Spain},
}

Sven Köhler, Christian Schindelhauer and Martin Ziegler. On Approximating Real-World Halting Problems. In

*Proceedings of the 15th International Symposium on Fundamentals of Computation Theory*, Springer, 2005, pp. 454–466. Lübeck, Germany.@InProceedings{KOEHLER_FCT05,
author = {Sven K{\"o}hler and Christian Schindelhauer and Martin Ziegler},
title = {On Approximating Real-World Halting Problems},
booktitle = {Proceedings of the 15th International Symposium on Fundamentals of Computation Theory},
pages = {454-466},
series = {Lecture Notes in Computer Science},
volume = {3623},
publisher = {Springer},
year = 2005,
location = {L{\"u}beck, Germany},
}

## PhD Theses

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.

## Students' Theses

Sven Köhler.

*Zur Praktikabilität schneller Polynomarithmetik*. Diploma Thesis, University of Paderborn, Paderborn, Germany, June 2007.@MastersThesis{KOEHLER_Diploma,
author = {Sven K{\"o}hler},
type = {Diploma Thesis},
title = {Zur Praktikabilit{\"a}t schneller Polynomarithmetik},
school = {University of Paderborn},
address = {Paderborn, Germany},
month = jun,
year = 2007,
}

Sven Köhler.

*Zur Approximierbarkeit des Halteproblems in einer praktischen Gödelisierung*. Bachelor's Thesis, University of Paderborn, Paderborn, Germany, June 2004.@MastersThesis{KOEHLER_Bachelor,
author = {Sven K{\"o}hler},
type = {Bachelor's Thesis},
title = {Zur Approximierbarkeit des Halteproblems in einer praktischen G{\"o}delisierung},
school = {University of Paderborn},
address = {Paderborn, Germany},
month = jun,
year = 2004,
}