15 Search Results for "Fischer, Stefan"

Document
DOI: 10.4230/LIPIcs.IPEC.2021.19
An Investigation of the Recoverable Robust Assignment Problem

Authors: Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We investigate the so-called recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ have at least k edges in common. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to parameter k, and also with respect to the complementary parameter k' = n/2-k. This hardness result holds even in the highly restricted special case where both cost functions c₁ and c₂ only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is Anti-Monge. Finally, we study the variant where matching M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², and we show that it is at least as hard as the infamous problem Exact Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing open problem.
Cite as

Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.IPEC.2021.19,
  author =	{Fischer, Dennis and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{An Investigation of the Recoverable Robust Assignment Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154025},
  doi =		{10.4230/LIPIcs.IPEC.2021.19},
  annote =	{Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
Document
DOI: 10.4230/DagRep.8.7.44
Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)

Authors: Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti

Published in: Dagstuhl Reports, Volume 8, Issue 7 (2019)

Abstract
From the 8th of July 2018 to the 13th of July 2018, a Dagstuhl Seminar took place with the topic "Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices". There, 40 participants from as many as 14 distinct countries and four distinct research areas, dealing with running time analysis and space usage analysis of algorithms and data structures, gathered to discuss results and techniques to "go beyond the worst-case" for classes of structurally restricted inputs, both for (fast) algorithms and (compressed) data structures. The seminar consisted of (1) a first session of personal introduction, each participant presenting his expertise and themes of interests in two slides; (2) a series of four technical talks; and (3) a larger series of presentations of open problems, with ample time left for the participants to gather and work on such open problems.
Cite as

Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{barbay_et_al:DagRep.8.7.44,
  author =	{Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao},
  title =	{{Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)}},
  pages =	{44--61},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{7},
  editor =	{Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.7.44},
  URN =		{urn:nbn:de:0030-drops-101724},
  doi =		{10.4230/DagRep.8.7.44},
  annote =	{Keywords: adaptive (analysis of) algorithms, compressed data structures, compressed indices, parameterized complexity}
}
Document
DOI: 10.4230/OASIcs.MCPS.2014.15
An Approach to Integrate Distributed Systems of Medical Devices in High Acuity Environments

Authors: David Gregorczyk, Stefan Fischer, Timm Busshaus, Stefan Schlichting, and Stephan Pöhlsen

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

Abstract
This paper presents a comprehensive solution to build a distributed system of medical devices in high acuity environments. It is based on the concept of a Service Oriented Medical Device Architecture. It uses the Devices Profile for Web Services as a transport layer protocol and enhances it to the Medical Devices Profile for Web Service (MDPWS) to meet medical requirements. By applying the ISO/IEEE 11073 Domain Information Model, device data can be semantically described and exchanged by means of a generic service interface. Data model and service interface are subsumed under the Basic Integrated Clinical Environment Specification (BICEPS). MDPWS and BICEPS are implemented as part of the publically available openSDC stack. Performance measurements and a real world setup prove that openSDC is feasible to be deployed in distributed systems of medical devices.
Cite as

David Gregorczyk, Stefan Fischer, Timm Busshaus, Stefan Schlichting, and Stephan Pöhlsen. An Approach to Integrate Distributed Systems of Medical Devices in High Acuity Environments. In 5th Workshop on Medical Cyber-Physical Systems. Open Access Series in Informatics (OASIcs), Volume 36, pp. 15-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gregorczyk_et_al:OASIcs.MCPS.2014.15,
  author =	{Gregorczyk, David and Fischer, Stefan and Busshaus, Timm and Schlichting, Stefan and P\"{o}hlsen, Stephan},
  title =	{{An Approach to Integrate Distributed Systems of Medical Devices in High Acuity Environments}},
  booktitle =	{5th Workshop on Medical Cyber-Physical Systems},
  pages =	{15--27},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.MCPS.2014.15},
  URN =		{urn:nbn:de:0030-drops-45191},
  doi =		{10.4230/OASIcs.MCPS.2014.15},
  annote =	{Keywords: Integrated Clinical Environment, Devices Profile for Web Services, ISO/IEEE 11073}
}
Document
DOI: 10.4230/OASIcs.KiVS.2011.26
A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems

Authors: Martin Lipphardt, Nils Glombitza, Jana Neumann, Christian Werner, and Stefan Fischer

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

Abstract
The paradigm of service-orientation promises a significant ease of use in creating and managing distributed software systems. A very important aspect here is that also application domain experts and stakeholders, who are not necessarily skilled in computer programming, get a chance to create, analyze, and adapt distributed applications. However, up to now, service-oriented architectures have been mainly discussed in the context of complex business applications. In this paper we will investigate how to transfer the benefits of a service-oriented architecture into the field of embedded systems, so that this technology gets accessible to a much wider range of users. As an example, we will demonstrate this scheme for sensor network applications. In order to address the problem of limited device resources we will introduce a minimal operating system for such devices. It organizes all pieces of code running on a sensor node in a service-oriented fashion and also features the relocation of code to a different node at runtime. We will demonstrate that it is possible to design a sensor network application from a set of already existing services in a highly modular way by employing already existing technologies and standards.
Cite as

Martin Lipphardt, Nils Glombitza, Jana Neumann, Christian Werner, and Stefan Fischer. A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 26-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{lipphardt_et_al:OASIcs.KiVS.2011.26,
  author =	{Lipphardt, Martin and Glombitza, Nils and Neumann, Jana and Werner, Christian and Fischer, Stefan},
  title =	{{A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{26--37},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.26},
  URN =		{urn:nbn:de:0030-drops-29550},
  doi =		{10.4230/OASIcs.KiVS.2011.26},
  annote =	{Keywords: service-oriented OS, sensor network, distributed embedded systems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.84
Satisfiability of Acyclic and Almost Acyclic CNF Formulas

Authors: Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We study the propositional satisfiability problem (SAT) on classes of CNF formulas (formulas in Conjunctive Normal Form) that obey certain structural restrictions in terms of their hypergraph structure, by associating to a CNF formula the hypergraph obtained by ignoring negations and considering clauses as hyperedges on variables. We show that satisfiability of CNF formulas with so-called ``beta-acyclic hypergraphs'' can be decided in polynomial time. We also study the parameterized complexity of SAT for ``almost'' beta-acyclic instances, using as parameter the formula's distance from being beta-acyclic. As distance we use the size of smallest strong backdoor sets and the beta-hypertree width. As a by-product we obtain the W[1]-hardness of SAT parameterized by the (undirected) clique-width of the incidence graph, which disproves a conjecture by Fischer, Makowsky, and Ravve (Discr. Appl. Math. 156, 2008).
Cite as

Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 84-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{ordyniak_et_al:LIPIcs.FSTTCS.2010.84,
  author =	{Ordyniak, Sebastian and Paulusma, Daniel and Szeider, Stefan},
  title =	{{Satisfiability of Acyclic and Almost Acyclic CNF Formulas}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{84--95},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.84},
  URN =		{urn:nbn:de:0030-drops-28556},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.84},
  annote =	{Keywords: Satisfiability, chordal bipartite graphs, beta-acyclic hypergraphs, backdoor sets, parameterized complexity}
}
Document
DOI: 10.4230/DagSemProc.09371.1
09371 Abstracts Collection – Algorithmic Methods for Distributed Cooperative Systems

Authors: Sándor Fekete, Stefan Fischer, Martin Riedmiller, and Suri Dubhash

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
From 06.09.09 to 11.09.09 the Dagstuhl Seminar 09371 ``Algorithmic Methods for Distributed Cooperative Systems'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The purpose of this workshop was to bring together researchers from different disciplines whose central interest is in both algorithmic foundations and application scenarios of distributed cooperative systems. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Sándor Fekete, Stefan Fischer, Martin Riedmiller, and Suri Dubhash. 09371 Abstracts Collection – Algorithmic Methods for Distributed Cooperative Systems. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.09371.1,
  author =	{Fekete, S\'{a}ndor and Fischer, Stefan and Riedmiller, Martin and Dubhash, Suri},
  title =	{{09371 Abstracts Collection – Algorithmic Methods for Distributed Cooperative Systems}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.1},
  URN =		{urn:nbn:de:0030-drops-25224},
  doi =		{10.4230/DagSemProc.09371.1},
  annote =	{Keywords: Algorithms, cooperative systems, sensor networks, multi-robot systems, applications}
}
Document
DOI: 10.4230/DagSemProc.09371.2
Cooperative Multi-Agent Systems from the Reinforcement Learning Perspective – Challenges, Algorithms, and an Application

Authors: Thomas Gabel

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
Reinforcement Learning has established as a framework that allows an autonomous agent for automatically acquiring – in a trial and error-based manner – a behavior policy based on a specification of the desired behavior of the system. In a multi-agent system, however, the decentralization of the control and observation of the system among independent agents has a significant impact on learning and it complexity. In this survey talk, we briefly review the foundations of single-agent reinforcement learning, point to the merits and challenges when applied in a multi-agent setting, and illustrate its potential in the context of an application from the field of manufacturing control and scheduling.
Cite as

Thomas Gabel. Cooperative Multi-Agent Systems from the Reinforcement Learning Perspective – Challenges, Algorithms, and an Application. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{gabel:DagSemProc.09371.2,
  author =	{Gabel, Thomas},
  title =	{{Cooperative Multi-Agent Systems from the Reinforcement Learning Perspective – Challenges, Algorithms, and an Application}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.2},
  URN =		{urn:nbn:de:0030-drops-24265},
  doi =		{10.4230/DagSemProc.09371.2},
  annote =	{Keywords: Multi-agent reinforcement learning, decentralized control, job-shop scheduling}
}
Document
DOI: 10.4230/DagSemProc.09371.3
Local Algorithms: Self-Stabilization on Speed

Authors: Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
An introduction to distributed algorithms, in particular local algorithms. Essentially a practice talk of my SSS 2009 invited talk.
Cite as

Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. Local Algorithms: Self-Stabilization on Speed. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lenzen_et_al:DagSemProc.09371.3,
  author =	{Lenzen, Christoph and Suomela, Jukka and Wattenhofer, Roger},
  title =	{{Local Algorithms: Self-Stabilization on Speed}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.3},
  URN =		{urn:nbn:de:0030-drops-24257},
  doi =		{10.4230/DagSemProc.09371.3},
  annote =	{Keywords: Local Algorithms, Self-Stabilization, Lower Bounds, Upper Bounds, MIS}
}
Document
DOI: 10.4230/DagSemProc.09371.4
On the Fairness of Probabilistic Schedulers for Population Protocols

Authors: Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
We propose a novel, generic definition of emph{probabilistic schedulers} for population protocols. We design two new schedulers, the emph{State Scheduler} and the emph{Transition Function Scheduler}. Both possess the significant capability of being emph{protocol-aware}, i.e. they can assign transition probabilities based on information concerning the underlying protocol. We prove that the proposed schedulers, and also the emph{Random Scheduler} that was defined by Angluin et al. cite{AADFP04}, are all fair with probability $1$. We also define and study emph{equivalence} between schedulers w.r.t. emph{performance} and emph{correctness} and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness. We implement our schedulers using a new tool for simulating population protocols and evaluate their performance from the viewpoint of experimental analysis and verification. We study three representative protocols to verify stability, and compare the experimental time to convergence with the known complexity bounds. We run our experiments from very small to extremely large populations (of up to $10^{8}$ agents). We get very promising results both of theoretical and practical interest.
Cite as

Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis. On the Fairness of Probabilistic Schedulers for Population Protocols. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chatzigiannakis_et_al:DagSemProc.09371.4,
  author =	{Chatzigiannakis, Ioannis and Dolev, Shlomi and Fekete, S\'{a}ndor and Michail, Othon and Spirakis, Paul},
  title =	{{On the Fairness of Probabilistic Schedulers for Population Protocols}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.4},
  URN =		{urn:nbn:de:0030-drops-24286},
  doi =		{10.4230/DagSemProc.09371.4},
  annote =	{Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation}
}
Document
DOI: 10.4230/DagSemProc.09371.5
On the Fundamental Limits of Broadcasting in Wireless Mobile Networks

Authors: Giovanni Resta and Paolo Santi

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
In this talk, we investigate the fundamental properties of broadcasting in mobile wireless networks. In particular, we characterize broadcast capacity and latency of a mobile network, subject to the condition that the stationary node spatial distribution generated by the mobility model is uniform. We first study the intrinsic properties of broadcasting, and present a broadcasting scheme, called RippleCast, that simultaneously achieves asymptotically optimal broadcast capacity and latency, subject to a weak upper bound on the maximum node velocity. This study intendedly ignores the burden related to the selection of broadcast relay nodes within the mobile network, and shows that optimal broadcasting in mobile networks is, in principle, possible. We then investigate the broadcasting problem when the relay selection burden is taken into account, and present a combined distributed leader election and broadcasting scheme achieving a broadcast capacity and latency which is within a $Theta((log n)^{1+frac{2}{alpha}})$ factor from optimal, where $n$ is the number of mobile nodes and $alpha>2$ is the path loss exponent. However, this result holds only under the assumption that the upper bound on node velocity converges to zero (although with a very slow, poly-logarithmic rate) as $n$ grows to infinity. To the best of our knowledge, our is the first paper investigating the effects of node mobility on the fundamental properties of broadcasting, and showing that, while optimal broadcasting in a mobile network is in principle possible, the coordination efforts related to the selection of broadcast relay nodes lead to sub-optimal broadcasting performance.
Cite as

Giovanni Resta and Paolo Santi. On the Fundamental Limits of Broadcasting in Wireless Mobile Networks. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{resta_et_al:DagSemProc.09371.5,
  author =	{Resta, Giovanni and Santi, Paolo},
  title =	{{On the Fundamental Limits of Broadcasting in Wireless Mobile Networks}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.5},
  URN =		{urn:nbn:de:0030-drops-24273},
  doi =		{10.4230/DagSemProc.09371.5},
  annote =	{Keywords: Wireless networks, mobile networks, broadcast capacity, broadcast latency, SINR interference model}
}
Document
DOI: 10.4230/DagSemProc.09371.6
Stabilizing Consensus with the Power of Two Choices

Authors: Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
Consensus problems occur in many contexts and have therefore been intensively studied in the past. In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Coming up with a self-stabilizing rule is easy without adversarial involvement, but we allow some T-bounded adversary to manipulate any T processes at any time. In this situation, a perfect consensus is impossible to reach, so we only require that there is a time point t and value v so that at any point after t, all but up to O(T) processes agree on v, which we call an almost stable consensus. As we will demonstrate, there is a surprisingly simple rule for the standard message passing model that just needs O(log n loglog n) time for any sqrt{n}-bounded adversary and just O(log n) time without adversarial involvement, with high probability, to reach an (almost) stable consensus from any initial state. A stable consensus is reached, with high probability, in the absence of adversarial involvement.
Cite as

Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing Consensus with the Power of Two Choices. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doerr_et_al:DagSemProc.09371.6,
  author =	{Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian},
  title =	{{Stabilizing Consensus with the Power of Two Choices}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.6},
  URN =		{urn:nbn:de:0030-drops-24290},
  doi =		{10.4230/DagSemProc.09371.6},
  annote =	{Keywords: Distributed consensus}
}
Document
DOI: 10.4230/DagSemProc.06481.2
Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs

Authors: Sándor Fekete, Alexander Kröller, Carsten Buschmann, and Stefan Fischer

Published in: Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)

Abstract
We present an approach to estimating distances in sensor networks. It works by counting common neighbors, high values indicating closeness. Such distance estimates are needed in many self-localization algorithms. Other than many other approaches, ours does not rely on special equipment in the devices.
Cite as

Sándor Fekete, Alexander Kröller, Carsten Buschmann, and Stefan Fischer. Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06481.2,
  author =	{Fekete, S\'{a}ndor and Kr\"{o}ller, Alexander and Buschmann, Carsten and Fischer, Stefan},
  title =	{{Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs}},
  booktitle =	{Geometric Networks and Metric Space Embeddings},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6481},
  editor =	{Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.2},
  URN =		{urn:nbn:de:0030-drops-10282},
  doi =		{10.4230/DagSemProc.06481.2},
  annote =	{Keywords: Sensor networks, distance estimation, unit disk graphs.}
}
Document
DOI: 10.4230/DagSemProc.05361.6
Deterministic boundary recongnition and topology extraction for large sensor networks

Authors: Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
We present a new framework for the crucial challenge of self-organization of a large sensor network. The basic scenario can be described as follows: Given a large swarm of immobile sensor nodes that have been scattered in a polygonal region, such as a street network. Nodes have no knowledge of size or shape of the environment or the position of other nodes. Moreover, they have no way of measuring coordinates, geometric distances to other nodes, or their direction. Their only way of interacting with other nodes is to send or to receive messages from any node that is within communication range. The objective is to develop algorithms and protocols that allow self-organization of the swarm into large-scale structures that reflect the structure of the street network, setting the stage for global routing, tracking and guiding algorithms. Our algorithms work in two stages: boundary recognition and topology extraction. All steps are strictly deterministic, yield fast distributed algorithms, and make no assumption on the distribution of nodes in the environment, other than sufficient density.
Cite as

Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer. Deterministic boundary recongnition and topology extraction for large sensor networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05361.6,
  author =	{Fekete, S\'{a}ndor and Kr\"{o}ller, Alexander and Pfisterer, Dennis and Fischer, Stefan},
  title =	{{Deterministic boundary recongnition and topology extraction for large sensor networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.6},
  URN =		{urn:nbn:de:0030-drops-5632},
  doi =		{10.4230/DagSemProc.05361.6},
  annote =	{Keywords: Distributed algorithms, sensor networks, boundary recognition, topology extraction}
}
Document
DOI: 10.4230/DagSemRep.358
Quality of Service in Networks and Distributed Systems (Dagstuhl Seminar 02441)

Authors: Andrew T. Campbell, Stefan Fischer, Klara Nahrstedt, and Lars Wolf

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Andrew T. Campbell, Stefan Fischer, Klara Nahrstedt, and Lars Wolf. Quality of Service in Networks and Distributed Systems (Dagstuhl Seminar 02441). Dagstuhl Seminar Report 358, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{campbell_et_al:DagSemRep.358,
  author =	{Campbell, Andrew T. and Fischer, Stefan and Nahrstedt, Klara and Wolf, Lars},
  title =	{{Quality of Service in Networks and Distributed Systems (Dagstuhl Seminar 02441)}},
  pages =	{1--10},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{358},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.358},
  URN =		{urn:nbn:de:0030-drops-152386},
  doi =		{10.4230/DagSemRep.358},
}
Document
DOI: 10.4230/DagSemRep.274
Quality of Service in Networks and Distributed Systems (Dagstuhl Seminar 00191)

Authors: Andrew Campbell, Domenico Ferrari, Stefan Fischer, and Lars Wolf

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Andrew Campbell, Domenico Ferrari, Stefan Fischer, and Lars Wolf. Quality of Service in Networks and Distributed Systems (Dagstuhl Seminar 00191). Dagstuhl Seminar Report 274, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{campbell_et_al:DagSemRep.274,
  author =	{Campbell, Andrew and Ferrari, Domenico and Fischer, Stefan and Wolf, Lars},
  title =	{{Quality of Service in Networks and Distributed Systems (Dagstuhl Seminar 00191)}},
  pages =	{1--19},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{274},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.274},
  URN =		{urn:nbn:de:0030-drops-151597},
  doi =		{10.4230/DagSemRep.274},
}
  • Refine by Author
  • 7 Fischer, Stefan
  • 4 Fekete, Sándor
  • 2 Kröller, Alexander
  • 2 Wolf, Lars
  • 1 Barbay, Jérémy
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 2 parameterized complexity
  • 2 sensor networks
  • 1 Algorithms
  • 1 Communicating Automata
  • 1 Devices Profile for Web Services
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 7 2010
  • 1 2000
  • 1 2003
  • 1 2006
  • 1 2007
  • Show More...

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