3 Search Results for "Murray, Alan T."

Document
DOI: 10.4230/LIPIcs.ECOOP.2024.42
Failure Transparency in Stateful Dataflow Systems

Authors: Aleksey Veresov, Jonas Spenger, Paris Carbone, and Philipp Haller

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract
Failure transparency enables users to reason about distributed systems at a higher level of abstraction, where complex failure-handling logic is hidden. This is especially true for stateful dataflow systems, which are the backbone of many cloud applications. In particular, this paper focuses on proving failure transparency in Apache Flink, a popular stateful dataflow system. Even though failure transparency is a critical aspect of Apache Flink, to date it has not been formally proven. Showing that the failure transparency mechanism is correct, however, is challenging due to the complexity of the mechanism itself. Nevertheless, this complexity can be effectively hidden behind a failure transparent programming interface. To show that Apache Flink is failure transparent, we model it in small-step operational semantics. Next, we provide a novel definition of failure transparency based on observational explainability, a concept which relates executions according to their observations. Finally, we provide a formal proof of failure transparency for the implementation model; i.e., we prove that the failure-free model correctly abstracts from the failure-related details of the implementation model. We also show liveness of the implementation model under a fair execution assumption. These results are a first step towards a verified stack for stateful dataflow systems.
Cite as

Aleksey Veresov, Jonas Spenger, Paris Carbone, and Philipp Haller. Failure Transparency in Stateful Dataflow Systems. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 42:1-42:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{veresov_et_al:LIPIcs.ECOOP.2024.42,
  author =	{Veresov, Aleksey and Spenger, Jonas and Carbone, Paris and Haller, Philipp},
  title =	{{Failure Transparency in Stateful Dataflow Systems}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{42:1--42:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.42},
  URN =		{urn:nbn:de:0030-drops-208911},
  doi =		{10.4230/LIPIcs.ECOOP.2024.42},
  annote =	{Keywords: Failure transparency, stateful dataflow, operational semantics, checkpoint recovery}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2023.4
Genetic Programming for Computationally Efficient Land Use Allocation Optimization

Authors: Moritz J. Hildemann, Alan T. Murray, and Judith A. Verstegen

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Land use allocation optimization is essential to identify ideal landscape compositions for the future. However, due to the solution encoding, standard land use allocation algorithms cannot cope with large land use allocation problems. Solutions are encoded as sequences of elements, in which each element represents a land unit or a group of land units. As a consequence, computation times increase with every additional land unit. We present an alternative solution encoding: functions describing a variable in space. Function encoding yields the potential to evolve solutions detached from individual land units and evolve fields representing the landscape as a single object. In this study, we use a genetic programming algorithm to evolve functions representing continuous fields, which we then map to nominal land use maps. We compare the scalability of the new approach with the scalability of two state-of-the-art algorithms with standard encoding. We perform the benchmark on one raster and one vector land use allocation problem with multiple objectives and constraints, with ten problem sizes each. The results prove that the run times increase exponentially with the problem size for standard encoding schemes, while the increase is linear with genetic programming. Genetic programming was up to 722 times faster than the benchmark algorithm. The improvement in computation time does not reduce the algorithm performance in finding optimal solutions; often, it even increases. We conclude that evolving functions enables more efficient land use allocation planning and yields much potential for other spatial optimization applications.
Cite as

Moritz J. Hildemann, Alan T. Murray, and Judith A. Verstegen. Genetic Programming for Computationally Efficient Land Use Allocation Optimization. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hildemann_et_al:LIPIcs.GIScience.2023.4,
  author =	{Hildemann, Moritz J. and Murray, Alan T. and Verstegen, Judith A.},
  title =	{{Genetic Programming for Computationally Efficient Land Use Allocation Optimization}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.4},
  URN =		{urn:nbn:de:0030-drops-188996},
  doi =		{10.4230/LIPIcs.GIScience.2023.4},
  annote =	{Keywords: Land use planning, Spatial optimization, Solution encoding, Computation time reduction}
}
Document
DOI: 10.4230/LIPIcs.GISCIENCE.2018.12
Heterogeneous Skeleton for Summarizing Continuously Distributed Demand in a Region

Authors: Alan T. Murray, Xin Feng, and Ali Shokoufandeh

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
There has long been interest in the skeleton of a spatial object in GIScience. The reasons for this are many, as it has proven to be an extremely useful summary and explanatory representation of complex objects. While much research has focused on issues of computational complexity and efficiency in extracting the skeletal and medial axis representations as well as interpreting the final product, little attention has been paid to fundamental assumptions about the underlying object. This paper discusses the implied assumption of homogeneity associated with methods for deriving a skeleton. Further, it is demonstrated that addressing heterogeneity complicates both the interpretation and identification of a meaningful skeleton. The heterogeneous skeleton is introduced and formalized, along with a method for its identification. Application results are presented to illustrate the heterogeneous skeleton and provides comparative contrast to homogeneity assumptions.
Cite as

Alan T. Murray, Xin Feng, and Ali Shokoufandeh. Heterogeneous Skeleton for Summarizing Continuously Distributed Demand in a Region. In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{murray_et_al:LIPIcs.GISCIENCE.2018.12,
  author =	{Murray, Alan T. and Feng, Xin and Shokoufandeh, Ali},
  title =	{{Heterogeneous Skeleton for Summarizing Continuously Distributed Demand in a Region}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{12:1--12:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.12},
  URN =		{urn:nbn:de:0030-drops-93400},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.12},
  annote =	{Keywords: Medial axis, Object center, Geographical summary, Spatial analytics}
}
  • Refine by Author
  • 2 Murray, Alan T.
  • 1 Carbone, Paris
  • 1 Feng, Xin
  • 1 Haller, Philipp
  • 1 Hildemann, Moritz J.
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Operations research
  • 1 Computing methodologies → Discrete space search
  • 1 Information systems → Geographic information systems
  • 1 Software and its engineering → Checkpoint / restart
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 1 Computation time reduction
  • 1 Failure transparency
  • 1 Geographical summary
  • 1 Land use planning
  • 1 Medial axis
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2023
  • 1 2024

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