Epidemic protocols assume that information of a random set of nodes is provided at each protocol round. By definition, the random set needs to be chosen uniformly and randomly from the entire set to gossip with. Consequently, a node observes a different set of randomly chosen nodes at each different protocol round. Several proposals have addressed the issue of providing a different random set of nodes at each different round. In general, for large systems, this is done by creating a partial view of the entire membership at each node and exchanging part of the partial view among nodes. While many interesting properties of this approach have been found, investigation is needed to study the performance of this approach with practically high network churn. Without an action specifically designed for churn, shuffling would produce many dangling pointers in the partial view which point to an already left node. This in turn would significantly degrade the quality of epidemic protocols. The reason for the poor quality of the partial view is that the procedures of leave and join can take too long time to handle churn efficiently. To address this issue, an additional action of reinforcement and a new join procedure are proposed and evaluated in this paper. The reinforcement detects and removes dangling pointers at each shuffle more effectively, and the new join procedure accommodates a newly joining node remarkably fast. The subsequent simulations show that these ideas enhance the shuffling mechanism such that the system processes network churn much faster and the quality of the node degrees is significantly enhanced.

In a fault-tolerant distributed system, it is often necessary for nonfaulty processes to agree on the value of a shared data item. The criterion of Approximate Agreement does not require processes to achieve exact agreement on a value; rather, they need only agree to within a predefined numerical tolerance. Approximate Agreement can be achieved through convergent voting algorithms. Previous research has studied convergent voting algorithms under mixed-mode or hybrid fault models, such as the Thambidurai and Park Hybrid fault model, comprised of three fault modes: asymmetric, symmetric, and benign. This paper makes three major contributions to the state of the art in fault-tolerant convergent voting. (1) We partition both the asymmetric and symmetric fault modes into disjoint omissive and transmissive submodes. The resulting five-mode hybrid fault model is a superset of previous hybrid fault models. (2) We present a new family of voting algorithms, called Omission Mean Subsequence Reduced (OMSR), which implicitly recognize and exploit omissive behavior in malicious faults while still maintaining full Byzantine fault tolerance; (3) We show that OMSR voting algorithms are more fault-tolerant than previous voting algorithms if any of the currently active faults is omissive.

An important problem in fault-tolerant distributed systems is maintaining agreement between nonfaulty processes in the presence of undiagnosed faults. To achieve agreement, processes exchange their local "opinions" of a particular value, and then vote on the values received to arrive at a "consensus". Approximate agreement defines a condition in which it is not necessary for consensus values to be identical. Rather, it is only necessary that they agree to within a predefined tolerance. Approximate agreement can be achieved through a sequence of convergent voting rounds, in which the range of values held by nonfaulty nodes is reduced in each round. Research has revealed simple expressions for the convergence rate and fault tolerance of a broad family of convergent voting algorithms called Mean-Subsequence-Reduced (MSR) algorithms. These results were derived under the Thambidurai and Park (1988) hybrid fault model comprised of asymmetric, symmetric, and benign faults. However, these results apply only to synchronous systems, in which there is a known finite bound on computation and communications times. We extend the previous results to asynchronous systems, in which no such bound exists. In addition, we introduce two new hybrid fault models which further differentiate between omissive faults and transmissive faults. The new fault models permit tighter bounds on the fault-tolerance of asynchronous systems to be derived.

In a fault-tolerant distributed system, different non-faulty processes may arrive at different values for a given system parameter. To resolve this disagreement, processes must exchange and vote upon their respective local values. Faulty processes may attempt to inhibit agreement by acting in a malicious or "Byzantine" manner. Approximate agreement defines one form of agreement in which the voted values obtained by the non-faulty processes need not be identical. Instead, they need only agree to within a predefined tolerance. Approximate agreement can be achieved by a sequence of convergent voting rounds, in which the range of values held by non-faulty processes is reduced in each round. Historically, each new convergent voting algorithm has been accompanied by ad-hoc proofs of its convergence rate and fault-tolerance, using an overly conservative fault model in which all faults exhibit worst-case Byzantine behavior. This paper presents a general method to quickly determine convergence rate and fault-tolerance for any member of a broad family of convergent voting algorithms. This method is developed under a realistic mixed-mode fault model comprised of asymmetric, symmetric, and benign fault modes. These results are employed to more accurately analyze the properties of several existing voting algorithms, to derive a sub-family of optimal mixed-mode voting algorithms, and to quickly determine the properties of proposed new voting algorithms.>

A description is given of the multicomputer architecture for fault tolerance (MAFT), a distributed system designed to provide extremely reliable computation in real-time control systems. MAFT is based on the physical and functional partitioning of executive functions from applications functions. The implementation of the executive functions in a special-purpose hardware processor allows the fault-tolerance functions to be transparent to the application programs and minimizes overhead. Byzantine agreement and approximate agreement algorithms are used for critical system parameters. MAFT supports the use of multiversion hardware and software to tolerate built-in or generic faults. Graceful degradation and restoration of the application workload is permitted in response to the exclusion and readmission of nodes, respectively.>