print page

Volker Turau

Picture of Volker Turau
Prof. Dr. rer. nat. Volker Turau
Room 4.088, building E
Am Schwarzenberg-Campus 3
21073 Hamburg
phone+49 40 42878 - 3530
fax+49 40 427 - 3 - 10456
e-mail

I am professor at Hamburg Universtity of Technology since October 2002.


Program Committee Activities | Editorial Activities | CV | Ph.D. students

Books

Algorithmische Graphentheorie - 4., extended and revised edition
De Gruyter Studium, 2015, ISBN 978-3-110-41727-2 (Solutions)

Erdős number

My Erdős number is 4.

Teaching

Publications

Volker Turau. A O(log n) Distributed Algorithm to Construct Routing Structures for Pub/Sub Systems. In 20th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS 2018), November 2018, pp. 65–79. Tokyo, Japan.
@InProceedings{Telematik_sss_2018, author = {Volker Turau}, title = {A O(log n) Distributed Algorithm to Construct Routing Structures for Pub/Sub Systems}, booktitle = {20th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS 2018)}, pages = {65-79}, day = {4-7}, month = nov, year = 2018, location = {Tokyo, Japan}, }
Volker Turau. A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time. In Lecture Notes in Computer Science - Proceedings of 25th International Colloquium on Structural Information and Communication Complexity (Scirocco 2018), June 2018, pp. 72–87. Ma'ale HaHamisha, Israel.
@InProceedings{Telematik_Scirocco_2018, author = {Volker Turau}, title = {A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time}, booktitle = {Lecture Notes in Computer Science - Proceedings of 25th International Colloquium on Structural Information and Communication Complexity (Scirocco 2018)}, pages = {72-87}, day = {18-21}, month = jun, year = 2018, location = {Ma'ale HaHamisha, Israel}, }
Abstract: It is known for some time that a random graph G(n, p) con- tains w.h.p. a Hamiltonian cycle if p is larger than the critical value pcrit = (log n+log log n+ωn)/n. The determination of a concrete Hamil- tonian cycle is even for values much larger than pcrit a nontrivial task. In this paper we consider random graphs G(n, p) with p in Ω ̃(1/√n), where Ω ̃ hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm AHC that finds w.h.p. a Hamiltonian cycle in O(log n) rounds. The algorithm works in the synchronous model and uses messages of size O(log n) and O(log n) memory per node.
Abdolhamid Ghodselahi, Fabian Kuhn and Volker Turau. Competitive Concurrent Distributed Scheduling. Technical Report arxiv:1902.07354, arXiv.org e-Print archive, Cornell University, February 2019.
@TechReport{Telematik_DSMS_2019, author = {Abdolhamid Ghodselahi and Fabian Kuhn and Volker Turau}, title = {Competitive Concurrent Distributed Scheduling}, number = {arxiv:1902.07354}, institution = {arXiv.org e-Print archive}, address = {Cornell University}, month = feb, year = 2019, }
Abstract: We introduce a new scheduling problem in distributed computing that we call the DSMS problem. We are given a set of k ≥ 1 mobile identical servers that are initially hosted by some processors of the given network. Further, we are given a set of requests that are issued by the processors possibly at any time in an online fashion, and the servers must serve them. A request must be scheduled before the request is served. The delay for scheduling a request is the time taken since the request is issued until it is scheduled. The goal is to minimize the average delay. Navigating mobile servers in a large-scale distributed system needs a scalable location service. We devise the distributed GNN protocol, a novel linked-reversal-based protocol for the DSMS problem that works on overlay trees. We prove that GNN is a starvation-free protocol that correctly integrates locating the servers and synchronizing the concurrent access to the servers despite asynchrony. Further, we analyze the GNN protocol for one-shot executions where all requests are simultaneously issued. We show that when running the GNN protocol on top of a special family of tree topologies---known as hierarchically well-separated trees (HSTs)---we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies for the DSMS problem where n is the number of processors in the given network. From a technical point of view, the main result of our paper shows that the GNN protocol optimally solves the DSMS problem on HSTs for one-shot executions. Our results hold even if communication is asynchronous.

The complete list of publications is available separately.