Design and Analysis of Highly Available Region-Adherent Distributed Algorithms in Faulty Environments

Design and Analysis of Highly Available Region-Adherent Distributed Algorithms in Faulty Environments

Bachelor or Master Thesis depending on workload

Topics

distributed systems, dependability, fault tolerance, region adherence, distributed algorithms design, distributed algorithms analysis

Background

This work is exploring a new class of fault-tolerant distributed algorithms based on a concept which we call region-adherence. A region-adherent algorithm upper-bound the violation of safety due to faults in space. With bounding in space, it is meant that the decrease of quality of the service which the system provides to its environment is upper-bounded per fault. When the number of faults that lead to failures of sub-systems are known, then a lower bound of the service quality provided by the system can be guaranteed. It is then up to the system user to decide, whether such a service quality is still acceptable or not.

Figure 1 gives a topological interpretation of the behavior of a region-adherent system. In the absence of any fault, the system is required to always stay in a region of the state space where the system is guaranteed to provide a service quality of 100%, indicated by the innermost region in the figure.

When the first fault happens, then - by the effect of the fault - the system may be "thrown" into the neighboring region of the state space. Here, a service quality of at least 100% - α is guaranteed. An alternative also allowed is that the system remains in the region, including included regions. Thus, after a second fault, the system is allowed to adopt system states belonging to any of the three innermost regions, thereby exhibiting a system quality of 100% - 2 · α minimum. So, contrary to a self-stabilizing system, where no minimum service quality can be assumed (for some time) even after the first fault, a region-adherent system, per fault up to some maximal number of faults, at most enters a neighboring region of the state space with a guaranteed service quality behavior. Thus, the system behavior is restricted in space since it is not allowed to transit into any other region. In this sense, the system adheres to regions of known system quality.

Task Description

The mission is to work on one or more of the following topics:

  1. Design of region-adherent systems;
  2. Discover methodologies of formally verifying the region adherence of a system;
  3. Systematic composition of region-adherent systems;
  4. Systematic refinement of their lower bounds of service quality known;
  5. Combining the concept of region adherence and self-stabilization.

If you have any even simple questions, please let us know and don't hesitate to contact us. For discussion and other issues, please do so as well. We will appreciate cooperate with you.

Language

The thesis should be written in German or English.

Contact

Prof. Dr.-Ing. Oliver Theel
Carl von Ossietzky Universität Oldenburg
Department für Informatik
Systemsoftware und verteilte Systeme

(Stand: 16.03.2023)  |