Narrow Results

We consider the problem of fault-tolerant parallel search on an infinite line by $n$ robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed $1$ and can communicate wirelessly among themselves. However, among the $n$ robots, there are $f$ robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient evidence that the target has been found. We aim to design algorithms that minimize the value of $S_d(n,f)$, the time to find a target at a (unknown) distance $d$ from the origin by $n$ robots among which $f$ are faulty. We give several different algorithms whose running time depends on the ratio $f/n$, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

This paper proposes a methodology for supporting the design of fault-tolerant computers for real-time applications. To this end, the paper first presents steps of fault tolerance and describes mechanisms that can be used to realize them. Then, the design options consisting of described mechanisms are proposed and a table summarizing them is designed. From that, the paper proposes a flowchart for choosing between the many various design options available for building a redundant computer system. Choosing an optimal design option is performed according to the number of redundant computers, the mode of operation of redundant computers, the computer failure mode and the severity of the real-time constraint. Finally, graphical models for sequencing the mechanisms of design options are proposed. The main merit of the proposed methodology includes a spectrum of design options of fault-tolerant mechanisms for real-time computers tolerating a single fault at a time and a guide for choosing between them.

Many crucial dependable and secure services including atomic commitment, consensus and group membership, and middleware services (such as replica, communication and transaction services) use fault detectors. Through the use of fault detectors, the overlying service can be exempted from failure treatment and synchronization requirements. Fault detection is essential for proving that the services carried out are correct.

In this paper, we first identify the necessary conditions to detect faults in a message passing system where multiple disjoint paths exist between each pair of endpoints. We then present the first fault detection protocol capable of detecting message meta-data modification in the presence of various message interferences in addition to other faults including omission faults, message replay and spurious messages using disjoint paths, where paths with faults are not known a priori. In addition, it authenticates message origins allowing Sybil attacks to be detected, identifies faulty paths, and classifies faults in the presence of multiple messages sent by various system processes. We establish the completeness and soundness properties of the proposed algorithm, i.e., it detects each considered fault and each detected fault is an actual fault, respectively. We also show that our algorithm does not yield a significant packet size and delay overheads. The algorithm shows the viability of the use of disjoint paths in fault detection.