Search Results

Documents authored by Turau, Volker

Document
DOI: 10.4230/LIPIcs.DISC.2024.28
Self-Stabilizing MIS Computation in the Beeping Model

Authors: George Giakkoupis, Volker Turau, and Isabella Ziccardi

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak beeping communication model. The model consists of an anonymous network with synchronous rounds. In each round, each vertex can optionally transmit a signal to all its neighbors (beep). After the transmission of a signal, each vertex can only differentiate between no signal received, or at least one signal received. We also consider an extension of this model where vertices can transmit signals through two distinguishable beeping channels. We assume that vertices have some knowledge about the topology of the network. We revisit the not self-stabilizing algorithm proposed by Jeavons, Scott, and Xu (2013), which computes an MIS in the beeping model. We enhance this algorithm to be self-stabilizing, and explore three different variants, which differ in the knowledge about the topology available to the vertices and the number of beeping channels. In the first variant, every vertex knows an upper bound on the maximum degree Δ of the graph. For this case, we prove that the proposed self-stabilizing version maintains the same run-time as the original algorithm, i.e., it stabilizes after O(log n) rounds w.h.p. on any n-vertex graph. In the second variant, each vertex only knows an upper bound on its own degree. For this case, we prove that the algorithm stabilizes after O(log n⋅ log log n) rounds on any n-vertex graph, w.h.p. In the third variant, we consider the model with two beeping channels, where every vertex knows an upper bound of the maximum degree of the nodes in the 1-hop neighborhood. We prove that this variant stabilizes w.h.p. after O(log n) rounds.
Cite as

George Giakkoupis, Volker Turau, and Isabella Ziccardi. Self-Stabilizing MIS Computation in the Beeping Model. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{giakkoupis_et_al:LIPIcs.DISC.2024.28,
  author =	{Giakkoupis, George and Turau, Volker and Ziccardi, Isabella},
  title =	{{Self-Stabilizing MIS Computation in the Beeping Model}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.28},
  URN =		{urn:nbn:de:0030-drops-212540},
  doi =		{10.4230/LIPIcs.DISC.2024.28},
  annote =	{Keywords: Maximal Independent Set, Self-Stabilization, Beeping Model}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.53
Concurrent Distributed Serving with Mobile Servers

Authors: Abdolhamid Ghodselahi, Fabian Kuhn, and Volker Turau

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are k identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol Gnn that solves the DSMS problem on overlay trees. We prove that Gnn is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze Gnn for "one-shot" executions, i.e., all requests are invoked simultaneously. We prove that when running Gnn 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 with n processors. From a technical point of view, our main result is that Gnn optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of Omega(max {k, log n/log log n}) on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.
Cite as

Abdolhamid Ghodselahi, Fabian Kuhn, and Volker Turau. Concurrent Distributed Serving with Mobile Servers. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ghodselahi_et_al:LIPIcs.ISAAC.2019.53,
  author =	{Ghodselahi, Abdolhamid and Kuhn, Fabian and Turau, Volker},
  title =	{{Concurrent Distributed Serving with Mobile Servers}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.53},
  URN =		{urn:nbn:de:0030-drops-115497},
  doi =		{10.4230/LIPIcs.ISAAC.2019.53},
  annote =	{Keywords: Distributed online resource allocation, Distributed directory, Asynchronous communication, Amortized analysis, Tree embeddings}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.MCPS.2014
OASIcs, Volume 36, MCPS'14, Complete Volume

Authors: Volker Turau, Marta Kwiatkowska, Rahul Mangharam, and Christoph Weyer

Published in: OASIcs, Volume 36, 5th Workshop on Medical Cyber-Physical Systems (2014)

Abstract
OASIcs, Volume 36, MCPS'14, Complete Volume
Cite as

5th Workshop on Medical Cyber-Physical Systems. Open Access Series in Informatics (OASIcs), Volume 36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{turau_et_al:OASIcs.MCPS.2014,
  title =	{{OASIcs, Volume 36, MCPS'14, Complete Volume}},
  booktitle =	{5th Workshop on Medical Cyber-Physical Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-66-8},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{36},
  editor =	{Turau, Volker and Kwiatkowska, Marta and Mangharam, Rahul and Weyer, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.MCPS.2014},
  URN =		{urn:nbn:de:0030-drops-45403},
  doi =		{10.4230/OASIcs.MCPS.2014},
  annote =	{Keywords: Conference proceedings}
}
Document
Front Matter
DOI: 10.4230/OASIcs.MCPS.2014.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Volker Turau, Marta Kwiatkowska, Rahul Mangharam, and Christoph Weyer

Published in: OASIcs, Volume 36, 5th Workshop on Medical Cyber-Physical Systems (2014)

Abstract
Frontmatter, Table of Contents, Preface, Workshop Organization
Cite as

5th Workshop on Medical Cyber-Physical Systems. Open Access Series in Informatics (OASIcs), Volume 36, pp. i-x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{turau_et_al:OASIcs.MCPS.2014.i,
  author =	{Turau, Volker and Kwiatkowska, Marta and Mangharam, Rahul and Weyer, Christoph},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{5th Workshop on Medical Cyber-Physical Systems},
  pages =	{i--x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-66-8},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{36},
  editor =	{Turau, Volker and Kwiatkowska, Marta and Mangharam, Rahul and Weyer, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.MCPS.2014.i},
  URN =		{urn:nbn:de:0030-drops-45174},
  doi =		{10.4230/OASIcs.MCPS.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.MCPS.2014.38
Adaptive Failure Detection and Correction in Dynamic Patient-Networks

Authors: Martin Ringwelski, Andreas Timm-Giel, and Volker Turau

Published in: OASIcs, Volume 36, 5th Workshop on Medical Cyber-Physical Systems (2014)

Abstract
Wireless sensors have been studied over recent years for different promising applications with high value for individuals and society. A good example are wireless sensor networks for patients allowing for better and more efficient monitoring of patients in hospitals or even early discharge form hospital and monitoring at home. These visions have hardly led research as reliability is and issue with wireless networks to be known error-prone. In life critical applications like health care this is not an aspect to be handled carelessly. Fail-safety is an important property for patient monitoring systems. The AA4R project of the Hamburg University of Technology researches on a fail-safe patient monitoring system. Our vision is a dynamically distributed system using suitable devices in the area of a patient. The data in the network is stored with redundancy on several nodes. Patient data is analyzed in the network and uploaded to a medical server. As devices appear, disappear and fail, so do the services being executed on those devices. This article focuses on a Reincarnation Service (RS) to track the functionality of the processes. The RS takes suitable actions when a failure is detected to correct or isolate the failure. Checking of the nodes is done adaptively to achieve a good response time to failures and reduce the power consumption.
Cite as

Martin Ringwelski, Andreas Timm-Giel, and Volker Turau. Adaptive Failure Detection and Correction in Dynamic Patient-Networks. In 5th Workshop on Medical Cyber-Physical Systems. Open Access Series in Informatics (OASIcs), Volume 36, pp. 38-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ringwelski_et_al:OASIcs.MCPS.2014.38,
  author =	{Ringwelski, Martin and Timm-Giel, Andreas and Turau, Volker},
  title =	{{Adaptive Failure Detection and Correction in Dynamic Patient-Networks}},
  booktitle =	{5th Workshop on Medical Cyber-Physical Systems},
  pages =	{38--48},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-66-8},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{36},
  editor =	{Turau, Volker and Kwiatkowska, Marta and Mangharam, Rahul and Weyer, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.MCPS.2014.38},
  URN =		{urn:nbn:de:0030-drops-45215},
  doi =		{10.4230/OASIcs.MCPS.2014.38},
  annote =	{Keywords: Wireless Sensor Networks, Fail-Safety, Health Monitoring, Failure Masking, Distributed Systems}
}
Document
DOI: 10.4230/OASIcs.KiVS.2011.97
Avoiding Publication and Privatization Problems on Software Transactional Memory

Authors: Holger Machens and Volker Turau

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)

Abstract
This paper presents a new approach to exclude problems arising from dynamically switching between protected concurrent and unprotected single-threaded use of shared data when using software transactional memory in OO languages such as Java. The approach is based on a simple but effective programming model separating transactions from non-transactional operation. It prevents the application programmer from errors but does not force the software transactional memory library to observe non-transactional access and thereby preserves modularity of the software. A prototypical toolchain for validation and source code instrumentation was implemented as a proof of concept.
Cite as

Holger Machens and Volker Turau. Avoiding Publication and Privatization Problems on Software Transactional Memory. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 97-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{machens_et_al:OASIcs.KiVS.2011.97,
  author =	{Machens, Holger and Turau, Volker},
  title =	{{Avoiding Publication and Privatization Problems on Software Transactional Memory}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{97--108},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.97},
  URN =		{urn:nbn:de:0030-drops-29614},
  doi =		{10.4230/OASIcs.KiVS.2011.97},
  annote =	{Keywords: Software Transactional Memory, Publication, Privatization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact