A model and a notation are developed for specifying the composition of concurrent programs. The work is based on the observation that the composition of concurrent programs often requires not only intraprocessor coordination but also interprocessor coordination. A notation is developed for explicitly specifying both forms of coordination within a single uniform framework. Much prior work has either ignored the interprocessor coordination aspects of composition, or treated it in a manner separate from the intraprocessor coordination aspects.>

In this paper we combine two previously disparate aspects of reliable distributed computing -selfstabllization, i.e., tolerance of systemic failures, and fault-tolerance, i.e., tolerance of process failures.We define what it means for a protocol to solve a problem while tolerating both types of failures and demonstrate a "compiler" that transforms a process failuretolerant protocol for a synchronous system into a process and systemic failure-tolerant protocol.For asynchronous systems, we present a protocol that solves a crucial problem (Consensus) while tolerating both process and systemic failures.

Self-stabilization is an abstraction of fault tolerance for transient malfunctions.Intuitively, a self-stabilizing program resumes normal behavior even if execution begins in an illegal initial state.In this paper, we explore the possibility of extending an arbitrary program into a self-stabilizing one.Our contributions are: (1) a formal definition of the concept of a program being a self-stabilizing extension of a non-stabilizing program; (2) a characterization of what properties may hold in such extensions; (3) a demonstration of the possibility of mechanically creating such extensions.The computational model used is that of an asynchronous distributed message-passing system whose communication topology is an arbitrary graph.We contrast the difficulties of self-stabilization in this model with those of the more common shared-memory models.

In a distributed consensus protocol all processors (of which t may be faulty) are given (binary) initial values; after exchanging messages all correct processors must agree on one of them. The quality of a protocol is measured here using as parameters the total number of processors n, number of rounds of message exchange r, and maximal message length m, with optima, respectively, of 3t+1, t+1, and 1. Although no known protocol is optimal in all these three aspects simultaneously, the protocols that take further steps in this direction are presented. The first protocol has n>4t, r=t+1, and polynomial message size. The second protocol has n>3t, r=3t+3, and m=2, and it is asymptotically optimal in all three quality parameters while using the optimal number of processors. Using these protocols as building blocks, families of protocols with intermediate quality parameters, offering better tradeoffs than previous results, are obtained. All the protocols work in polynomial time and have succinct descriptions.>

Parallel algorithms and computational complexity results are given for two problems; computing the relative complement of terms and antiunification. The concepts of antiunification and relative complement are useful for theorem proving, logic programming, and machine learning. The relative complement problem is shown to be NP-complete.>

We describe a Byzantine Agreement algorithm, with early stopping, for systems with arbitrary process failures. The algorithm presented is simpler and more efficient than those previously known. It was derived using a broadcast primitive that provides properties of message authentication and thus restricts the disruptive behavior of faulty processes. This primitive is a general tool for deriving fault-tolerant algorithms in the presence of arbitrary failures.

A model of distributed computation is proposed in which processes may fail by not sending or receiving the message specified by a protocol. The solution to the Byzantine generals problem for this model is presented. The algorithm exhibits early stopping under conditions of less than maximum failure and is as efficient as the algorithm developed for the more restrictive crash-fault model in terms of time, message, and bit complexity. The authors show extant models to underestimate resiliency when faults in the communication medium are considered; the model outlined here is more accurate in this regard.

We describe a non-authenticated Byzantine Generals algorithm, with early stopping, for systems with arbitrary process failures.The algorithm presented is simpler, terminates earlier and has a lower communication complexity than those previously known.Surprisingly, the earlystopping algorithm is as efficient as previously proposed algorithms that do not exhibit the early-stopping property.It was derived using a broadcast primitive that simulates authentication and thus restricts the visible failure behavior of faulty processes.This primitive is a general tool for deriving fault-tolerant algorithms in the presence of arbitrary failures.

A randomized model of distributed computation was recently presented by Rabin [ 81. This model admits a solution to the Byzantine Agreement Problem for systems of n asynchronous processes where no more than t are faulty. The algorithm described by Rabin produces agreement in an expected number of rounds which is a small constant independent of n and t. Using the same model, we present an algorithm of similar complexity which is able to tolerate a greater portion of malicious processes. The algorithm is also applicable, with minor changes, to systems of synchronous processes.