Publications on Fault Tolerance

• Do Not Overpay for Fault Tolerance! Edo Roth and Andreas Haeberlen. 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21), May 2021.
  
  × @inproceedings{roth-2021-byzantine,
    author = {Edo Roth and Andreas Haeberlen},
    title = {Do Not Overpay for Fault Tolerance!},
    booktitle = {27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21)},
    doi = {10.1109/RTAS52030.2021.00037},
    month = may,
    year = 2021
  }
  ×

  In this paper, we argue that distributed real-time and embedded systems sometimes 'overpay' for fault tolerance, by using a protocol that is more powerful than what is actually needed, or by failing to take advantage of unique features in these systems. As a result, these systems sometimes perform more computation or communication than is strictly necessary, or they can be unnecessarily complex, and thus more difficult to analyze.

  We take a look at the design space for two common problems, broadcast and consensus, and we show that, in a number of scenarios that would be common in real-time systems, these problems have trivial solutions. We then examine two solutions from the literature and propose alternatives that are substantially simpler, less expensive, and more reliable.

  PDF BibTeX Abstract Slides Talk
• DNA: Dynamic Resource Allocation for Soft Real-Time Multicore Systems. Robert Gifford, Neeraj Gandhi, Linh Thi Xuan Phan, and Andreas Haeberlen. 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21), May 2021.
  
  × @inproceedings{gifford-2021-dna,
    author = {Robert Gifford and Neeraj Gandhi and Linh Thi Xuan Phan and Andreas Haeberlen},
    title = {{DNA}: {D}ynamic Resource Allocation for Soft Real-Time Multicore Systems},
    booktitle = {27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21)},
    doi = {10.1109/RTAS52030.2021.00024},
    month = may,
    year = 2021
  }
  ×

  Modern latency-sensitive and real-time systems often use multi-core platforms; thus, tasks on different cores share certain hardware resources, such as the memory bus and certain cache levels. This has two undesirable consequences: (1) tasks can interfere with each other, causing high latency for the system as a whole, and (2) it becomes difficult to meet deadlines, since the worst-case timing of a given task depends on the worst task it might have to compete with. Static partitioning isolates tasks from each other by allocating a certain fraction of the resources to each; however, many tasks execute in different phases (e.g., memory-intensive and CPU-intensive) that have different requirements. Thus, system designers are left with a choice between overprovisioning, based on the most demanding phase, or suboptimal performance.

  In this paper, we propose a pair of techniques, called DNA and DADNA, to address the above challenge. DNA increases throughput and decreases latency, by building an execution profile of each task to identify the phases, and then dynamically allocating resources based on which task can benefit the most; DADNA further adds support for soft real-time workloads by taking deadlines into account. We have built a prototype of both techniques in the Xen hypervisor; our experimental results show that, compared to a state-of-the-art solution, DNA and DADNA can substantially improve schedulability, reduce job deadline miss ratios, and cut latencies by more than a factor of two even in extremely overloaded situations.

  PDF BibTeX Abstract Talk
• REBOUND: Defending Distributed Systems Against Attacks with Bounded-Time Recovery. Neeraj Gandhi, Edo Roth, Brian Sandler, Andreas Haeberlen, and Linh Thi Xuan Phan. 16th European Conference on Computer Systems (EuroSys '21), Apr 2021.
  
  × @inproceedings{gandhi-2021-rebound,
    author = {Neeraj Gandhi and Edo Roth and Brian Sandler and Andreas Haeberlen and Linh Thi Xuan Phan},
    title = {{REBOUND}: {D}efending Distributed Systems Against Attacks with {B}ounded-{T}ime {R}ecovery},
    booktitle = {16th European Conference on Computer Systems (EuroSys '21)},
    doi = {10.1145/3447786.3456257},
    month = apr,
    year = 2021
  }
  ×

  This paper shows how to use bounded-time recovery (BTR) to defend distributed systems against non-crash faults and attacks. Unlike many existing fault-tolerance techniques, BTR does not attempt to completely mask all symptoms of a fault; instead, it ensures that the system returns to the correct behavior within a bounded amount of time. This weaker guarantee is sufficient, e.g., for many cyber-physical systems, where physical properties – such as inertia and thermal capacity – prevent quick state changes and thus limit the damage that can result from a brief period of undefined behavior.

  We present an algorithm called REBOUND that can provide BTR for the Byzantine fault model. REBOUND works by detecting faults and then reconfiguring the system to exclude the faulty nodes. This supports very fine-grained responses to faults: for instance, the system can move or replace existing tasks, or drop less critical tasks entirely to conserve resources. REBOUND can take useful actions even when a majority of the nodes is compromised, and it requires less redundancy than full fault-tolerance.

  PDF BibTeX Abstract Neeraj's slides Talk
• Bounded-Time Recovery for Distributed Real-Time Systems. Neeraj Gandhi, Edo Roth, Robert Gifford, Linh Thi Xuan Phan, and Andreas Haeberlen. 26th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '20), Apr 2020.
  
  × @inproceedings{gandhi-2020-cascade,
    author = {Neeraj Gandhi and Edo Roth and Robert Gifford and Linh Thi Xuan Phan and Andreas Haeberlen},
    title = {Bounded-Time Recovery for Distributed Real-Time Systems},
    booktitle = {26th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '20)},
    month = apr,
    year = 2020
  }
  ×

  This paper explores bounded-time recovery (BTR), a new approach to making cyber-physical systems robust to crash faults. Rather than trying to mask the symptoms of a fault with massive redundancy, BTR detects faults at runtime and enables the system to recover from them – e.g., by transferring tasks to other nodes that are still working correctly. When a fault does occur, there is a brief period of instability during which the system can produce incorrect outputs. However, many cyber-physical systems have physical properties – such as inertia or thermal capacity – that limit the rate at which the state of the system can change; thus, a very brief outage is often acceptable, as long as its duration can be bounded, to perhaps a few milliseconds.

  BTR has some interesting properties: for instance, it has a much lower overhead than Paxos, and, unlike Paxos, it can take useful actions even when the system partitions or a majority of the nodes fails. However, it also poses a very unusual scheduling problem that involves creating sets of interrelated schedules for different failure modes. We present a scheduling algorithm called Cascade that can quickly find suitable schedules. Using a prototype implementation, we show that Cascade scales far better than a baseline algorithm and reduces the scheduling time from hours to a few seconds, without sacrificing quality.

  PDF BibTeX Abstract Neeraj's slides Talk
• Fault Tolerance and the Five-Second Rule. Ang Chen, Hanjun Xiao, Andreas Haeberlen, and Linh Thi Xuan Phan. 15th Workshop on Hot Topics in Operating Systems (HotOS XV), Kartause Ittingen, Switzerland, May 2015.
  
  × @inproceedings{chen-2015-btr,
    author = {Ang Chen and Hanjun Xiao and Andreas Haeberlen and Linh Thi Xuan Phan},
    title = {Fault Tolerance and the Five-Second Rule},
    booktitle = {15th Workshop on Hot Topics in Operating Systems (HotOS XV)},
    location = {Kartause Ittingen, Switzerland},
    month = may,
    year = 2015
  }
  ×

  We propose a new approach to fault tolerance that we call bounded-time recovery (BTR). BTR is intended for systems that need strong timeliness guarantees during normal operation but can tolerate short outages in an emergency, e.g., when they are under attack. We argue that BTR could be a good fit for many cyber-physical systems. We also sketch a technical approach to providing BTR, and we discuss some challenges that still remain.

  PDF BibTeX Abstract Slides

Show all publications