DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.23

Ensuring Average Recovery with Adversarial Scheduler

Authors: Jingshu Chen, Mohammad Roohitavaf, and Sandeep S. Kulkarni

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

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.

Cite as

Jingshu Chen, Mohammad Roohitavaf, and Sandeep S. Kulkarni. Ensuring Average Recovery with Adversarial Scheduler. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

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

Search Results

Documents authored by Chen, Jingshu

Ensuring Average Recovery with Adversarial Scheduler

Abstract

Cite as

Thanks for your feedback!

Could not send message