Byzantine Generals protocols enable processes to broadcast messages reliably in the presence of faulty processes. These protocols are run in a system that consists of n processes, t of which are faulty. The protocols are conducted in synchronous rounds of message exchange. It is shown that, in the absence of eavesdropping, without using cryptography, for any ε > 0 and t = n /(3 + ε), there is a randomized protocol with O (log n ) expected number of rounds. If cryptographic methods are allowed, then, for ε > 0 and t = n /(2 + ε), there is a randomized protocol with O (log n ) expected number of rounds. This is an improvement on the lower bound of t + 1 rounds required for deterministic protocols, and on a previous result of t /log n expected number of rounds for randomized noncryptographic protocols.

Byzantine Generals protocols enable processes to reliably broadcast messages in the presence of faulty processes. These protocols are run in a system of consists of n processes, t of which are faulty. The protocols are conducted in synchronous rounds of message exchange. We show that, without using cryptography, for t = n/(3 + d), there is a randomized protocol with O(lg n) expected number of rounds. If we allow cryptographic methods, then, for t = n / (2 + d), there is a randomized protocol with O(lg n) expected number of rounds. This is an improvement on the lower bound of t + 1 rounds required for det … … previous result of t/lg n expected nu rounds for randomized protocols.

A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can also send false messages. The class of asynchronous systems with fair schedulers is defined, and consensus protocols that terminate with probability 1 for these systems are investigated. With fail-stop processes, it is shown that ⌈( n + 1)/2⌉ correct processes are necessary and sufficient to reach agreement. In the malicious case, it is shown that ⌈(2 n + 1)/3⌉ correct processes are necessary and sufficient to reach agreement. This is contrasted with an earlier result, stating that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. The possibility of reliable broadcast (Byzantine Agreement) in asynchronous systems is also investigated. Asynchronous Byzantine Agreement is defined, and it is shown that ⌈(2 n + 1)/3⌉ correct processes are necessary and sufficient to achieve it.

A consensus protocol enables a system of n asynchronous processes, some of them malicious, to reach agreement. No assumptions are made on the behaviour of the processes and the message system; both are capable of colluding to prevent the correct processes from reaching decision. A protocol is t-resilient if in the presence of up to t malicious processes it reaches agreement with probability 1. In a recent paper, t-resilient consensus protocols were presented for t<n/5. We improve this to t

An efficient distributed algorithm to detect deadlocks in distributed and dynamically changing systems is presented. In our model, processes can request any $N$ available resources from a pool of size $M$. This is a generalization of the well-known AND-OR request model. The algorithm is incrementally derived and proven correct. Its communication, computational, and space complexity compares favorably to those of previously known distributed AND-OR deadlock detection algorithms.

A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes can only die, malicious processes can also send false messages. We investigate consensus protocols that terminate within finite time with probability 1 under certain assumptions on the behavior of the system. With fail-stop processes, we show that [(n + 1)/2] correct processes are necessary and sufficient to reach agreement. In the malicious case, we show that [(2n + 1)/3] correct processes are necessary and sufficient to reach agreement. This is contrasted with a recent result that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail.