2 Search Results for "Baumg�rtner, Lars"

Document
DOI: 10.4230/LIPIcs.ECOOP.2018.1
Fault-tolerant Distributed Reactive Programming

Authors: Ragnar Mogk, Lars Baumgärtner, Guido Salvaneschi, Bernd Freisleben, and Mira Mezini

Published in: LIPIcs, Volume 109, 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Abstract
In this paper, we present a holistic approach to provide fault tolerance for distributed reactive programming. Our solution automatically stores and recovers program state to handle crashes, automatically updates and shares distributed parts of the state to provide eventual consistency, and handles errors in a fine-grained manner to allow precise manual control when necessary. By making use of the reactive programming paradigm, we provide these mechanisms without changing the behavior of existing programs and with reasonable performance, as indicated by our experimental evaluation.
Cite as

Ragnar Mogk, Lars Baumgärtner, Guido Salvaneschi, Bernd Freisleben, and Mira Mezini. Fault-tolerant Distributed Reactive Programming. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mogk_et_al:LIPIcs.ECOOP.2018.1,
  author =	{Mogk, Ragnar and Baumg\"{a}rtner, Lars and Salvaneschi, Guido and Freisleben, Bernd and Mezini, Mira},
  title =	{{Fault-tolerant Distributed Reactive Programming}},
  booktitle =	{32nd European Conference on Object-Oriented Programming (ECOOP 2018)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-079-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{109},
  editor =	{Millstein, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2018.1},
  URN =		{urn:nbn:de:0030-drops-92064},
  doi =		{10.4230/LIPIcs.ECOOP.2018.1},
  annote =	{Keywords: reactive programming, distributed systems, CRDTs, snapshots, restoration, error handling, fault tolerance}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.315
Combinatorial Redundancy Detection

Authors: Komei Fukuda, Bernd Gärtner, and May Szedlák

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in n+d variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving n+d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves n+d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable x_r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for x_r. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time of order d (n+d) s^{d-1} LP(s,d) + d s^{d} LP(n,d) to detect all redundancies. In the case where all constraints are in general position, the running time is of order s LP(n,d) + (n+d) LP(s,d), which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.
Cite as

Komei Fukuda, Bernd Gärtner, and May Szedlák. Combinatorial Redundancy Detection. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 315-328, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fukuda_et_al:LIPIcs.SOCG.2015.315,
  author =	{Fukuda, Komei and G\"{a}rtner, Bernd and Szedl\'{a}k, May},
  title =	{{Combinatorial Redundancy Detection}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{315--328},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.315},
  URN =		{urn:nbn:de:0030-drops-51434},
  doi =		{10.4230/LIPIcs.SOCG.2015.315},
  annote =	{Keywords: system of linear inequalities, redundancy removal, linear programming, output sensitive algorithm, Clarkson’s method}
}
  • Refine by Author
  • 1 Baumgärtner, Lars
  • 1 Freisleben, Bernd
  • 1 Fukuda, Komei
  • 1 Gärtner, Bernd
  • 1 Mezini, Mira
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Data flow languages
  • 1 Software and its engineering → Software fault tolerance

  • Refine by Keyword
  • 1 CRDTs
  • 1 Clarkson’s method
  • 1 distributed systems
  • 1 error handling
  • 1 fault tolerance
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2018

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