License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2015.23
URN: urn:nbn:de:0030-drops-65907
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6590/
Go to the corresponding LIPIcs Volume Portal

Chen, Jingshu ; Roohitavaf, Mohammad ; Kulkarni, Sandeep S.

Ensuring Average Recovery with Adversarial Scheduler

pdf-format:
LIPIcs-OPODIS-2015-23.pdf (0.6 MB)

Abstract

In this paper, we focus on revising a given program so that the average recovery time in the presence of an adversarial scheduler is bounded by a given threshold lambda. Specifically, we consider the scenario where the fault (or other unexpected action) perturbs the program to a state that is outside its set of legitimate states. Starting from this state, the program executes its actions/transitions to recover to legitimate states. However, the adversarial scheduler can force the program to reach one illegitimate state that requires a longer recovery time.

To ensure that the average recovery time is less than lambda, we need to remove certain transitions/behaviors. We show that achieving this average response time while removing minimum transitions is NP-hard. In other words, there is a tradeoff between the time taken to synthesize the program and the transitions preserved to reduce the average convergence time. We present six different heuristics and evaluate this tradeoff with case studies. Finally, we note that the average convergence time considered here requires formalization of hyperproperties. Hence, this work also demonstrates feasibility of adding (certain) hyperproperties to an existing program.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2016:6590,
  author =	{Jingshu Chen and Mohammad Roohitavaf and Sandeep S. Kulkarni},
  title =	{{Ensuring Average Recovery with Adversarial Scheduler}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6590},
  URN =		{urn:nbn:de:0030-drops-65907},
  doi =		{10.4230/LIPIcs.OPODIS.2015.23},
  annote =	{Keywords: Average Recovery Time, Hyper-liveness, Program Repair}
}

Keywords: Average Recovery Time, Hyper-liveness, Program Repair
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI