Byzantine consensus in asynchronous message-passing systems: a survey
---
paper_title: Secure and efficient asynchronous broadcast protocols (extended abstract

paper_content:

Broadcast protocols are a fundamental building block for implementing replication in fault-tolerant distributed systems. This paper addresses secure service replication in an asynchronous environment with a static set of servers, where a malicious adversary may corrupt up to a threshold of servers and controls the network. We develop a formal model using concepts from modern cryptography, give modular definitions for several broadcast problems, including reliable, atomic, and secure causal broadcast, and present protocols implementing them. Reliable broadcast is a basic primitive, also known as the Byzantine generals problem, providing agreement on a delivered message. Atomic broadcast imposes additionally a total order on all delivered messages. We present a randomized atomic broadcast protocol based on a new, efficient multi-valued asynchronous Byzantine agreement primitive with an external validity condition. Apparently, no such efficient asynchronous atomic broadcast protocol maintaining liveness and safety in the Byzantine model has appeared previously in the literature. Secure causal broadcast extends atomic broadcast by encryption to guarantee a causal order among the delivered messages. Our protocols use threshold cryptography for signatures, encryption, and coin-tossing.
---
paper_title: Separating agreement from execution for byzantine fault tolerant services

paper_content:

We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages over previous architectures. First, it reduces replication costs because the new architecture can tolerate faults in up to half of the state machine replicas that execute requests. Previous systems can tolerate faults in at most a third of the combined agreement/state machine replicas. Second, separating agreement from execution allows a general privacy firewall architecture to protect confidentiality through replication. In contrast, replication in previous systems hurts confidentiality because exploiting the weakest replica can be sufficient to compromise the system. We have constructed a prototype and evaluated it running both microbenchmarks and an NFS server. Overall, we find that the architecture adds modest latencies to unreplicated systems and that its performance is competitive with existing Byzantine fault tolerant systems.
---
paper_title: Distributed agreement and its relation with error-correcting codes

paper_content:

The condition based approach identifies sets of input vectors, called conditions, for which it is possible to design a protocol solving a distributed problem despite process crashes. This paper investigates three related agreement problems, namely consensus, interactive consistency, and k-set agreement, in the context of the condition-based approach. In consensus, processes have to agree on one of the proposed values; in interactive consistency, they have to agree on the vector of proposed values; in k-set agreement, each process decides on one of the proposed values, and at most k different values can be decided on. For both consensus and interactive consistency, a direct correlation between these problems and error correcting codes is established. In particular, crash failures in distributed agreement problems correspond to erasure failures in error correcting codes, and Byzantine and value domain faults correspond to corruption errors. It is also shown that less restrictive codes can be used to solve k-set agreement, but without a necessity proof, which is still an open problem.
---
paper_title: Solving vector consensus with a wormhole

paper_content:

This paper presents a solution to the vector consensus problem for Byzantine asynchronous systems augmented with wormholes. Wormholes prefigure a hybrid distributed system model, embodying the notion of an enhanced part of the system with "good" properties otherwise not guaranteed by the "normal" weak environment. A protocol built for this type of system runs in the asynchronous part, where f out of n/spl ges/3f+1 processes might be corrupted by malicious adversaries. However, sporadically, processes can rely on the services provided by the wormhole for the correct execution of simple operations. One of the nice features of this setting is that it is possible to keep the protocol completely time-free and, in addition, to circumvent the FLP impossibility result by hiding all time-related assumptions in the wormhole. Furthermore, from a performance perspective, it leads to the design of a protocol with a good time complexity.
---
paper_title: Wait-free synchronization

paper_content:

A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a concensus protocol, for proving statements of the form, “there is no wait-free implementation of X by Y.” We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: thay cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as test&set and fetch&add , while more powerful than read and write , are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.
---
paper_title: Security , trust , and QoS in next-generation control and communication for large power systems

paper_content:

The present communication architecture supporting control of the electric power grid makes it difficult to use the wealth of data collected at high rates in substations, retarding their use in new applications for controlling the grid. A flexible, real-time data network would make it possible to use these data for many more control and protection applications, potentially increasing the grid's reliability and increasing its operating efficiency. Applications that could use these data include: decentralised load frequency control; closed-loop voltage control; transient and small-signal stabilisation; and special protection schemes using data gathered over a wide area. Such applications and the flexibility of the underlying communication network imply greater data sharing between utilities, leading to new performance, availability and reliability requirements. This paper examines the security, trust and Quality of Service (QoS) requirements imposed by these applications and shows how they are met by mechanisms included in the GridStat middleware framework that we are developing.
---
paper_title: Consensus in Asynchronous Distributed Systems: A Concise Guided Tour

paper_content:

It is now recognized that the Consensus problem is a fundamental problem when one has to design and implement reliable asynchronous distributed systems. This chapter is on the Consensus problem. It studies Consensus in two failure models, namely, the Crash/no Recovery model and the Crash/Recovery model. The assumptions related to the detection of failures that are required to solve Consensus in a given model are particularly emphasized.
---
paper_title: Sharing Memory between Byzantine Processes Using Policy-Enforced Tuple Spaces

paper_content:

Despite the large amount of Byzantine fault-tolerant algorithms for message-passing systems designed through the years, only recently algorithms for the coordination of processes subject to Byzantine failures using shared memory have appeared. This paper presents a new computing model in which shared memory objects are protected by fine-grained access policies, and a new shared memory object, the policy-enforced augmented tuple space (PEATS). We show the benefits of this model by providing simple and efficient consensus algorithms. These algorithms are much simpler and use less memory bits than previous algorithms based on ACLs and sticky bits. We also prove that PEATSs are universal (they can be used to implement any shared memory object), and present a universal construction.
---
paper_title: Reaching Agreement in the Presence of Faults

paper_content:

The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor. It is shown that the problem is solvable for, and only for, n ≥ 3 m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods.
---
paper_title: Attested append-only memory: making adversaries stick to their word

paper_content:

Researchers have made great strides in improving the fault tolerance of both centralized and replicated systems against arbitrary (Byzantine) faults. However, there are hard limits to how much can be done with entirely untrusted components; for example, replicated state machines cannot tolerate more than a third of their replica population being Byzantine. In this paper, we investigate how minimal trusted abstractions can push through these hard limits in practical ways. We propose Attested Append-Only Memory (A2M), a trusted system facility that is small, easy to implement and easy to verify formally. A2M provides the programming abstraction of a trusted log, which leads to protocol designs immune to equivocation -- the ability of a faulty host to lie in different ways to different clients or servers -- which is a common source of Byzantine headaches. Using A2M, we improve upon the state of the art in Byzantine-fault tolerant replicated state machines, producing A2M-enabled protocols (variants of Castro and Liskov's PBFT) that remain correct (linearizable) and keep making progress (live) even when half the replicas are faulty, in contrast to the previous upper bound. We also present an A2M-enabled single-server shared storage protocol that guarantees linearizability despite server faults. We implement A2M and our protocols, evaluate them experimentally through micro- and macro-benchmarks, and argue that the improved fault tolerance is cost-effective for a broad range of uses, opening up new avenues for practical, more reliable services.
---
paper_title: Highly-Resilient Services for Critical Infrastructures

paper_content:

Modern society depends on several critical infrastructures like power, water, oil and gas generation and distribution. These infrastructures have evolved to become largely controlled by computers and interconnected by computer networks, which lets them exposed to the same types of threats as Internet systems. Therefore, research about mechanisms to improve the protection of these infrastructures is extremely important. Byzantine fault-tolerant (BFT) replication algorithms tackle this problem by allowing critical services, like storage and processing of monitoring data, to continue to operate correctly even if some of their components are compromised by malicious attackers. This paper proposes a novel BFT algorithm that requires fewer replicas, fewer communication steps and analytically seems to have better throughput and latency than others in literature. The main idea is to provide an efficient BFT algorithm suitable to WANs, to be applied in the construction of highly-resilient services for critical infrastructures, tolerating even the physical destruction of some servers.
---
paper_title: Implementing fault-tolerant services using the state machine approach: a tutorial

paper_content:

The state machine approach is a general method for implementing fault-tolerant services in distributed systems. This paper reviews the approach and describes protocols for two different failure models—Byzantine and fail stop. Systems reconfiguration techniques for removing faulty components and integrating repaired components are also discussed.
---
paper_title: Impossibility of distributed consensus with one faulty process

paper_content:

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the "Byzantine Generals" problem.
---
paper_title: The Crutial Way of Critical Infrastructure Protection

paper_content:

Critical infrastructures are essentially physical processes controlled by networked computers. They're usually as vulnerable as any other interconnected computer system, but their failure has a high socioeconomic impact. The critical utility infrastructural resilience (Crutial) information switch is an intrusion-tolerant and self-healing device designed to protect these critical infrastructures.
---
paper_title: Consensus: The Big Misunderstanding

paper_content:

The paper aims at clarifying some misunderstandings about the consensus problem. These misunderstandings prevent consensus from being considered as it should be, i.e., a fundamental paradigm in the context of fault-tolerant distributed systems, not only from a theoretical point of view, but also from a practical point of view. Six frequent misunderstandings are discussed.
---
paper_title: From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures

paper_content:

This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical distributed systems: multi-valued consensus, vector consensus and atomic broadcast. These protocols are designed as successive transformations from one to another. The first protocol, multi-valued consensus, is implemented on top of a randomized binary consensus and a reliable broadcast protocol. The protocols share a set of important structural properties. First, they do not use digital signatures constructed with public-key cryptography, a well-known performance bottleneck in this kind of protocols. Second, they are time-free, i.e. they make no synchrony assumptions, since these assumptions are often vulnerable to subtle but effective attacks. Third, they are completely decentralized, thus avoiding the cost of detecting corrupt leaders. Fourth, they have optimal resilience, i.e. they tolerate the failure of f = ⌊(n-1)/3⌋ out of a total of n processes. In terms of time complexity, the multi-valued consensus protocol terminates in a constant expected number of rounds, while the vector consensus and atomic broadcast protocols have O(f) complexity. The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures. A similar proof is given for the equivalence between multi-valued consensus and vector consensus. These two results have theoretical relevance since they show once more that consensus is a fundamental problem in distributed systems.
---
paper_title: Objects Shared by Byzantine Processes

paper_content:

Work to date on algorithms for message-passing systems has explored a wide variety of types of faults, but corresponding work on shared memory systems has usually assumed that only crash faults are possible. In this work, we explore situations in which processes accessing shared objects can fail arbitrarily (Byzantine faults).
---
paper_title: Practical byzantine fault tolerance and proactive recovery

paper_content:

Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2p faster to 24p slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults.
---
paper_title: Unreliable intrusion detection in distributed computations

paper_content:

Distributed coordination is difficult, especially when the system may suffer intrusions that corrupt some component processes. We introduce the abstraction of a failure detector that a process can use to (imperfectly) detect the corruption (Byzantine failure) of another process. In general, our failure detectors can be unreliable, both by reporting a correct process to be faulty or by reporting a faulty process to be correct. However, we show that if these detectors satisfy certain plausible properties, then the well known distributed consensus problem can be solved. We also present a randomized protocol using failure detectors that solves the consensus problem if either the requisite properties of failure detectors hold or if certain highly probable events eventually occur. This work can be viewed as a generalization of benign failure detectors popular in the distributed computing literature.
---
paper_title: Tight Bounds for Shared Memory Systems Accessed by Byzantine Processes

paper_content:

We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine faults, in a model previously explored by Malkhi et al. [MMRT00]. We show that sticky bits are universal in the Byzantine failure model for n ? 3t + 1, an improvement over the previous result requiring n ? (2t+1)(t+1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n ?= 3t + 1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects.
---
paper_title: The Generic Consensus Service

paper_content:

This paper describes a modular approach for the construction of fault-tolerant agreement protocols. The approach is based on a generic consensus service. Fault-tolerant agreement protocols are built using a client-server interaction, where the clients are the processes that must solve the agreement problem and the servers implement the consensus service. This service is accessed through a generic consensus filter, customized for each specific agreement problem. We illustrate our approach on the construction of various fault-tolerant agreement protocols, such as nonblocking atomic commitment, group membership, view synchronous communication, and total order multicast. Through a systematic reduction to consensus, we provide a simple way to solve agreement problems. In addition to its modularity, our approach enables efficient implementations of agreement protocols and precise characterization of the assumptions underlying their liveness and safety properties.
---
paper_title: On the minimal synchronism needed for distributed consensus

paper_content:

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.
---
paper_title: Consensus in the presence of partial synchrony

paper_content:

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound P on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and P exist. In one version of partial synchrony, fixed bounds Δ and P exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and P. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T , and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
---
paper_title: Consensus in Byzantine asynchronous systems

paper_content:

This paper presents a consensus protocol resilient to Byzantine failures. It uses signed and certified messages and is based on two underlying failure detection modules. The first is a muteness failure detection module of the class ♦M. The second is a reliable Byzantine behaviour detection module. More precisely, the first module detects processes that stop sending messages, while processes experiencing other non-correct behaviours (i.e., Byzantine) are detected by the second module. The protocol is resilient to F faulty processes, F ≤ min(⌊(n - 1)/2⌋, C) (where C is the maximum number of faulty processes that can be tolerated by the underlying certification service).The approach used to design the protocol is new. While usual Byzantine consensus protocols are based on failure detectors to detect processes that stop communicating, none of them use a module to detect their Byzantine behaviour (this detection is not isolated from the protocol and makes it difficult to understand and prove correct). In addition to this modular approach and to a consensus protocol for Byzantine systems, the paper presents a finite state automaton-based implementation of the Byzantine behaviour detection module. Finally, the modular approach followed in this paper can be used to solve other problems in asynchronous systems experiencing Byzantine failures.
---
paper_title: Reaching Agreement in the Presence of Faults

paper_content:

The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor. It is shown that the problem is solvable for, and only for, n ≥ 3 m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods.
---
paper_title: Paxos At War

paper_content:

The optimistic latency of Byzantine Paxos can be reduced from three communication steps to two, without using public-key cryptography. This is done by making a decision when more than (n + 3f)/2 acceptors report to have received the same proposal from the leader, with n being the total number of acceptors and f the number of the faulty ones. No further improvement in latency is possible, because every Consensus algorithm must take at least two steps even in benign settings. Moreover, if the leader is correct, our protocol achieves the latency of at most three steps, even if some other processes fail. These two properties make this the fastest Byzantine agreement protocol proposed so far. By running many instances of this algorithm in parallel, we can implement Vector Consensus and Byzantine Atomic Broadcast in two and three steps, respectively, which is two steps faster than any other known algorithm.
---
paper_title: Fast Byzantine Consensus

paper_content:

We present the first consensus protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication step, and number of processes for 2-step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case.
---
paper_title: Implementing fault-tolerant services using the state machine approach: a tutorial

paper_content:

The state machine approach is a general method for implementing fault-tolerant services in distributed systems. This paper reviews the approach and describes protocols for two different failure models—Byzantine and fail stop. Systems reconfiguration techniques for removing faulty components and integrating repaired components are also discussed.
---
paper_title: On k-set Consensus Problems in Asynchronous Systems

paper_content:

In this paper, we investigate the k-set consensus problem in asynchronous distributed systems. In this problem, each participating process begins the protocol with an input value and by the end of the protocol must decide on one value so that at most k total values are decided by all correct processes. We extend previous work by exploring several variations of the problem definition and model, including for the first time investigation of Byzantine failures. We show that the precise definition of the validity requirement, which characterizes what decision values are allowed as a function of the input values and whether failures occur, is crucial to the solvability of the problem. For example, we show that allowing default decisions in case of failures makes the problem solvable for most values of k despite a minority of failures, even in face of the most severe type of failures (Byzantine). We introduce six validity conditions for this problem (all considered in various contexts in the literature), and demarcate the line between possible and impossible for each case. In many cases, this line is different from the one of the originally studied k-set consensus problem.
---
paper_title: Byzantine Fault Detectors for Solving Consensus

paper_content:

Unreliable fault detectors can be defined in terms of completeness and accuracy properties and can be used to solve the consensus problem in asynchronous distributed systems that are subject to crash faults. We extend this result to asynchronous distributed systems that are subject to Byzantine faults. First, we define and categorize Byzantine faults. We then define two new completeness properties, eventual strong completeness and eventual weak completeness. We use these completeness properties and previously defined accuracy properties to define four new classes of unreliable Byzantine fault detectors. Next, we present an algorithm that uses a Byzantine fault detector to solve the consensus problem in an asynchronous distributed system of n processes in which the number k of Byzantine faults satisfies k ≤� (n − 1)/3� . We also give algorithms that implement a Byzantine fault detector in a model of partial synchrony. Finally, we prove the correctness of the consensus algorithm and analyze its complexity.
---
paper_title: A pleasant stroll through the land of infinitely many creatures

paper_content:

Many distributed algorithms are designed for a system with a fixed set of n processes. However, some systems may dynamically change and expand over time,so that the number of processes may grow to infinity as time tends to infinity. This paper considers such systems, and gives algorithms that are new and simple (but not necessarily efficient) for common problems. The reason for simplicity is to better expose some of the algorithmic techniques for dealing with infinitely many processes. A brief summary of existing work in the subject is also provided.
---
paper_title: Practical byzantine fault tolerance and proactive recovery

paper_content:

Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2p faster to 24p slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults.
---
paper_title: Unreliable intrusion detection in distributed computations

paper_content:

Distributed coordination is difficult, especially when the system may suffer intrusions that corrupt some component processes. We introduce the abstraction of a failure detector that a process can use to (imperfectly) detect the corruption (Byzantine failure) of another process. In general, our failure detectors can be unreliable, both by reporting a correct process to be faulty or by reporting a faulty process to be correct. However, we show that if these detectors satisfy certain plausible properties, then the well known distributed consensus problem can be solved. We also present a randomized protocol using failure detectors that solves the consensus problem if either the requisite properties of failure detectors hold or if certain highly probable events eventually occur. This work can be viewed as a generalization of benign failure detectors popular in the distributed computing literature.
---
paper_title: Muteness Failure Detectors: Specification and Implementation

paper_content:

This paper extends the failures detector approach from crash-stop failures to muteness failures. Muteness failures are malicious failures in which a process stops sending algorithm messages, but might continue to send other messages, e.g., "I-am-alive" messages. The paper presents both the specification of a muteness failure detector, denoted by ⋄MA, and an implementation of ⋄MA in a partial synchrony model (there are bounds on message latency and clock skew, but these bounds are unknown and hold only after some point that is itself unknown). We show that, modulo a simple modification a consensus algorithm that has been designed in a crash-stop model with ⋄S, can be reused in the presence of muteness failures simply by replacing ⋄MA with ⋄S.
---
paper_title: The ABCD's of Paxos

paper_content:

We explain how consensus is used to implement replicated state machines, the general mechanism for fault-tolerance. We describe an abstract version of Lamport's Paxos algorithm for asynchronous consensus. Then we derive the Byzantine, classic, and disk versions of Paxos from the abstract one, show how they are related to each other, and discuss the safety, liveness, and performance of each one.
---
paper_title: HQ replication: a hybrid quorum protocol for byzantine fault tolerance

paper_content:

There are currently two approaches to providing Byzantine-fault-tolerant state machine replication: a replica-based approach, e.g., BFT, that uses communication between replicas to agree on a proposed ordering of requests, and a quorum-based approach, such as Q/U, in which clients contact replicas directly to optimistically execute operations. Both approaches have shortcomings: the quadratic cost of inter-replica communication is un-necessary when there is no contention, and Q/U requires a large number of replicas and performs poorly under contention. We present HQ, a hybrid Byzantine-fault-tolerant state machine replication protocol that overcomes these problems. HQ employs a lightweight quorum-based protocol when there is no contention, but uses BFT to resolve contention when it arises. Furthermore, HQ uses only 3f + 1 replicas to tolerate f faults, providing optimal resilience to node failures. We implemented a prototype of HQ, and we compare its performance to BFT and Q/U analytically and experimentally. Additionally, in this work we use a new implementation of BFT designed to scale as the number of faults increases. Our results show that both HQ and our new implementation of BFT scale as f increases; additionally our hybrid approach of using BFT to handle contention works well.
---
paper_title: Byzantine consensus with unknown participants

paper_content:

Consensus is a fundamental building block used to solve many practical problems that appear on reliable distributed systems. In spite of the fact that consensus is being widely studied in the context of classical networks, few studies have been conducted in order to solve it in the context of dynamic and self-organizing systems characterized by unknown networks. While in a classical network the set of participants is static and known, in a scenario of unknown networks, the set and number of participants are previously unknown. This work goes one step further and studies the problem of Byzantine Fault-Tolerant Consensus with Unknown Participants , namely BFT-CUP. This new problem aims at solving consensus in unknown networks with the additional requirement that participants in the system can behave maliciously. This paper presents a solution for BFT-CUP that does not require digital signatures. The algorithms are shown to be optimal in terms of synchrony and knowledge connectivity among participants in the system.
---
paper_title: Consensus in the presence of partial synchrony

paper_content:

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound P on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and P exist. In one version of partial synchrony, fixed bounds Δ and P exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and P. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T , and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
---
paper_title: More Choices Allow More Faults: Set Consensus Problems In Totally Asynchronous Systems

paper_content:

Abstract We define the k -SET CONSENSUS PROBLEM as an extension of the CONSENSUS problem, where each processor decides on a single value such that the set of decided values in any run is of size at most k . We require the agreement condition that all values decided upon are initial values of some processor. We show that the problem has a simple ( k −1)-resilient protocol in a totally asynchronous system. In an attempt to come up with a matching lower bound on the number of failures, we study the uncertainty condition, which requires that there must be some initial configuration from which all possible input values can be decided. We prove using a combinatorial argument that any k -resilient protocol for the k -set agreement problem would satisfy the uncertainty condition, while this is not true for any ( k −1)-resilient protocol. This result seems to strengthen the conjecture that there is no k -resilient protocol for this problem. We prove this result for a restricted class of protocols. Our motivation for studying this problem is to test whether the number of choices allowed to the processors is related to the number of faults . We hope that this will provide intuition towards achieving better bounds for more practical problems that arise in distributed computing, e.g., the renaming problem. The larger goal is to characterize the boundary between possibility and impossibility in asynchronous systems given multiple faults.
---
paper_title: Distributed agreement and its relation with error-correcting codes

paper_content:

The condition based approach identifies sets of input vectors, called conditions, for which it is possible to design a protocol solving a distributed problem despite process crashes. This paper investigates three related agreement problems, namely consensus, interactive consistency, and k-set agreement, in the context of the condition-based approach. In consensus, processes have to agree on one of the proposed values; in interactive consistency, they have to agree on the vector of proposed values; in k-set agreement, each process decides on one of the proposed values, and at most k different values can be decided on. For both consensus and interactive consistency, a direct correlation between these problems and error correcting codes is established. In particular, crash failures in distributed agreement problems correspond to erasure failures in error correcting codes, and Byzantine and value domain faults correspond to corruption errors. It is also shown that less restrictive codes can be used to solve k-set agreement, but without a necessity proof, which is still an open problem.
---
paper_title: Randomized Byzantine Agreements

paper_content:

Randomized algorithms for reaching Byzantine Agreement were recently proposed in [Rabi83]. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes n and the number of faulty processes t . The algorithms in [Rabi83] tolerate up to [( n -1)/10] faulty processes in asynchronous systems, and up to [( n -1)/4] faulty processes in synchronous systems. In this paper, using the same computation model as in [Rabi83], we describe algorithms that overcome up to [( n -1)/3] faulty processes in asynchronous systems, and up to [( n -1)/2] faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of n and t , but the communication complexity is higher than in [Rabi83]. It is also shown that no Byzantine Agreement algorithm can overcome more than [( n -1)/3] faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.
---
paper_title: Impossibility of distributed consensus with one faulty process

paper_content:

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the "Byzantine Generals" problem.
---
paper_title: The information structure of indulgent consensus

paper_content:

To solve consensus, distributed systems have to be equipped with oracles such as a failure detector, a leader capability, or a random number generator. For each oracle, various consensus algorithms have been devised. Some of these algorithms are indulgent toward their oracle in the sense that they never violate consensus safety, no matter how the underlying oracle behaves. We present a simple and generic indulgent consensus algorithm that can be instantiated with any specific oracle and be as efficient as any ad hoc consensus algorithm initially devised with that oracle in mind. The key to combining genericity and efficiency is to factor out the information structure of indulgent consensus executions within a new distributed abstraction, which we call "Lambda". Interestingly, identifying this information structure also promotes a fine-grained study of the inherent complexity of indulgent consensus. We show that instantiations of our generic algorithm with specific oracles, or combinations of them, match lower bounds on oracle-efficiency, zero-degradation, and one-step-decision. We show, however, that no leader or failure detector-based consensus algorithm can be, at the same time, zero-degrading and configuration-efficient. Moreover, we show that leader-based consensus algorithms that are oracle-efficient are inherently zero-degrading, but some failure detector-based consensus algorithms can be both oracle-efficient and configuration-efficient. These results highlight some of the fundamental trade offs underlying each oracle.
---
paper_title: On the minimal synchronism needed for distributed consensus

paper_content:

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.
---
paper_title: A hundred impossibility proofs for distributed computing

paper_content:

Abstract : This talk is about impossibility results in the area of distributed computing. In this category, I include not just results that say that a particular task cannot be accomplished, but also lower bound results, which say that a task cannot be accomplished within a certain bound on cost. I started out with a simple plan for preparing this talk: I would spend a couple of weeks reading all the impossibility proofs in our fields, and would categorize them according to the ideas used. Then I would make wise and general observations, and try to predict where the future of this area is headed. That turned out to be a bit too ambitious; there are many more such results than I thought. Although it is often hard to say what constitutes ad different results, I managed to count over 100 such impossibility proofs And my search wasn't even very systematic or exhaustive. It's not quite as hopeless to understand this area as it might seem from the number of papers. Although there are 100 different results, there aren't 100 different ideas. I thought I could contribute something by identifying some of the commonality among the different results.
---
paper_title: Experimental Comparison of Local and Shared Coin Randomized Consensus Protocols

paper_content:

The paper presents a comparative performance study of the two main classes of randomized binary consensus protocols: a local coin protocol, with an expected high communication complexity and cheap symmetric cryptography, and a shared coin protocol, with an expected low communication complexity and expensive asymmetric cryptography. The experimental evaluation was conducted on a LAN environment, by varying several system parameters, such as the fault types and number of processes. The analysis shows that there is a significant gap between the theoretical and the practical performance results of these protocols, and provides an important insight into what actually happens during their execution.
---
paper_title: Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography

paper_content:

Byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are maliciously misbehaving. A new protocol for Byzantine agreement in a completely asynchronous network is presented that makes use of new cryptographic protocols, specifically protocols for threshold signatures and coin-tossing. These cryptographic protocols have practical and provably secure implementations in the random oracle model. In particular, a coin-tossing protocol based on the Diffie-Hellman problem is presented and analyzed. The resulting asynchronous Byzantine agreement protocol is both practical and theoretically optimal because it tolerates the maximum number of corrupted parties, runs in constant expected rounds, has message and communication complexity close to the optimum, and uses a trusted dealer only once in a setup phase, after which it can process a virtually unlimited number of transactions. The protocol is formulated as a transaction processing service in a cryptographic security model, which differs from the standard information-theoretic formalization and may be of independent interest.
---
paper_title: Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems

paper_content:

This paper is on the consensus problem in asynchronous distributed systems where (up to f) processes (among n) can exhibit a Byzantine behavior, i.e., can deviate arbitrarily from their specification. One way to solve the consensus problem in such a context consists of enriching the system with additional oracles that are powerful enough to cope with the uncertainty and unpredictability created by the combined effect of Byzantine behavior and asynchrony. This paper presents two kinds of Byzantine asynchronous consensus protocols using two types of oracles, namely, a common coin that provides processes with random values and a failure detector oracle. Both allow the processes to decide in one communication step in favorable circumstances. The first is a randomized protocol for an oblivious scheduler model that assumes n > 6f. The second one is a failure detector-based protocol that assumes n > tif. These protocols are designed to be particularly simple and efficient in terms of communication steps, the number of messages they generate in each step, and the size of messages. So, although they are not optimal in the number of Byzantine processes that can be tolerated, they are particularly efficient when we consider the number of communication steps they require to decide and the number and size of the messages they use. In that sense, they are practically appealing.
---
paper_title: Randomized Byzantine Agreements

paper_content:

Randomized algorithms for reaching Byzantine Agreement were recently proposed in [Rabi83]. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes n and the number of faulty processes t . The algorithms in [Rabi83] tolerate up to [( n -1)/10] faulty processes in asynchronous systems, and up to [( n -1)/4] faulty processes in synchronous systems. In this paper, using the same computation model as in [Rabi83], we describe algorithms that overcome up to [( n -1)/3] faulty processes in asynchronous systems, and up to [( n -1)/2] faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of n and t , but the communication complexity is higher than in [Rabi83]. It is also shown that no Byzantine Agreement algorithm can overcome more than [( n -1)/3] faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.
---
paper_title: Randomized Intrusion-Tolerant Asynchronous Services

paper_content:

Randomized agreement protocols have been around for more than two decades. Often assumed to be inefficient due to their high expected communication and time complexities, they have remained largely overlooked by the community-at-large as a valid solution for the deployment of fault-tolerant distributed systems. This paper aims to demonstrate that randomization can be a very competitive approach even in hostile environments where arbitrary faults can occur. A stack of randomized intrusion-tolerant protocols is described and its performance evaluated under different faultloads. The stack provides a set of relevant services ranging from basic communication primitives up to atomic broadcast. The experimental evaluation shows that the protocols are efficient and no performance reduction is observed under certain Byzantine faults.
---
paper_title: An asynchronous [(n - 1)/3]-resilient consensus protocol

paper_content:

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 n /3, thus matching the lower bound on the number of correct processes necessary for consensus. The protocol restricts the behaviour of the malicious processes to that of merely fail-stop processes, which makes it interesting in other contexts.
---
paper_title: Consensus in the presence of partial synchrony

paper_content:

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound P on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and P exist. In one version of partial synchrony, fixed bounds Δ and P exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and P. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T , and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
---
paper_title: Consensus in the presence of partial synchrony

paper_content:

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound P on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and P exist. In one version of partial synchrony, fixed bounds Δ and P exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and P. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T , and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
---
paper_title: A methodology to design arbitrary failure detectors for distributed protocols q

paper_content:

Nowadays, there are many protocols able to cope with process crashes, but, unfortunately, a process crash represents only a particular faulty behavior. Handling tougher failures (e.g. sending omission failures, receive omission failures, arbitrary failures) is a real practical challenge due to malicious attacks or unexpected software errors. This is usually achieved either by changing, in an ad hoc manner, the code of a crash resilient protocol or by devising a new protocol from scratch. This paper proposes an alternative methodology to detect processes experiencing arbitrary failures. On this basis, it introduces the notions of liveness failure detector and safety failure detector as two independent software components. With this approach, the nature of failures experienced by processes becomes transparent to the protocol using the components. This methodology brings a few advantages: it makes possible to increase the resilience of a protocol designed in a crash failure context without changing its code by concentrating only on the design of a few well-specified components, and second, it clearly separates the task of designing the protocol from the task of detecting faulty processes, a methodological improvement. Finally, the feasibility of this approach is shown, by providing an implementation of liveness failure detectors and of safety failure detectors for two protocols: one solving the consensus, and the second solving the problem of global data computation.
---
paper_title: Consensus in Byzantine asynchronous systems

paper_content:

This paper presents a consensus protocol resilient to Byzantine failures. It uses signed and certified messages and is based on two underlying failure detection modules. The first is a muteness failure detection module of the class ♦M. The second is a reliable Byzantine behaviour detection module. More precisely, the first module detects processes that stop sending messages, while processes experiencing other non-correct behaviours (i.e., Byzantine) are detected by the second module. The protocol is resilient to F faulty processes, F ≤ min(⌊(n - 1)/2⌋, C) (where C is the maximum number of faulty processes that can be tolerated by the underlying certification service).The approach used to design the protocol is new. While usual Byzantine consensus protocols are based on failure detectors to detect processes that stop communicating, none of them use a module to detect their Byzantine behaviour (this detection is not isolated from the protocol and makes it difficult to understand and prove correct). In addition to this modular approach and to a consensus protocol for Byzantine systems, the paper presents a finite state automaton-based implementation of the Byzantine behaviour detection module. Finally, the modular approach followed in this paper can be used to solve other problems in asynchronous systems experiencing Byzantine failures.
---
paper_title: Asynchronous Byzantine consensus with 2f+1 processes

paper_content:

Byzantine consensus in asynchronous message-passing systems has been shown to require at least 3f + 1 processes to be solvable in several system models (e.g., with failure detectors, partial synchrony or randomization). Recently a couple of solutions to implement Byzantine fault-tolerant state-machine replication using only 2f + 1 replicas have appeared. This reduction from 3f + 1 to 2f + 1 is possible with a hybrid system model, i.e., by extending the system model with trusted/trustworthy components that constrain the power of faulty processes to have certain behaviors. Despite these important results, the problem of solving Byzantine consensus with only 2f + 1 processes is still far from being well understood. In this paper we present a methodology to transform crash consensus algorithms into Byzantine consensus algorithms with different characteristics, with the assistance of a reliable broadcast primitive that requires trusted/trustworthy components to be implemented. We exemplify the methodology with two algorithms, one that uses failure detectors and one that is randomized. We also define a new flavor of consensus and use it to solve atomic broadcast, showing the practical interest of the transformations.
---
paper_title: Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems

paper_content:

This paper is on the consensus problem in asynchronous distributed systems where (up to f) processes (among n) can exhibit a Byzantine behavior, i.e., can deviate arbitrarily from their specification. One way to solve the consensus problem in such a context consists of enriching the system with additional oracles that are powerful enough to cope with the uncertainty and unpredictability created by the combined effect of Byzantine behavior and asynchrony. This paper presents two kinds of Byzantine asynchronous consensus protocols using two types of oracles, namely, a common coin that provides processes with random values and a failure detector oracle. Both allow the processes to decide in one communication step in favorable circumstances. The first is a randomized protocol for an oblivious scheduler model that assumes n > 6f. The second one is a failure detector-based protocol that assumes n > tif. These protocols are designed to be particularly simple and efficient in terms of communication steps, the number of messages they generate in each step, and the size of messages. So, although they are not optimal in the number of Byzantine processes that can be tolerated, they are particularly efficient when we consider the number of communication steps they require to decide and the number and size of the messages they use. In that sense, they are practically appealing.
---
paper_title: Solving Agreement Problems with Weak Ordering Oracles

paper_content:

Agreement problems, such as consensus, atomic broadcast, and group membership, are central to the implementation of fault-tolerant distributed systems. Despite the diversity of algorithms that have been proposed for solving agreement problems in the past years, almost all solutions are Crash-Detection Based (CDB). We say that an algorithm is CDB if it uses some information about the status crashed/not crashed of processes. In this paper, we revisit the issue of non-CDB algorithms considering ordering oracles. Ordering oracles have a theoretical interest as well as a practical interest. To illustrate their use, we present solutions to consensus and atomic broadcast, and evaluate the performance of the atomic broadcast algorithm in a cluster of workstations.
---
paper_title: Tolerating Arbitrary Failures with State Machine Replication

paper_content:

The growing reliance, in our daily lives, on services provided by distributed applications (e.g., air-traffic control, public switched telephone networks, electronic commerce, etc.) renders us vulnerable to the failures of these services. The challenge of fault tolerance consists in providing services that survive to the occurrence of failures. The design and verification of fault-tolerant distributed applications is however viewed as a difficult task. In recent years, several paradigms have fortunately been identified which simplify this task. Key among these paradigms is state machine replication [12, 15, 19]. The underlying idea is intuitively simple. In short, every crucial service that needs to be made fault tolerant is replicated on several computers that are supposed to fail independently. The presence of several replicas ensures the high availability of the service. To preserve the consistency of the service, invocations of its replicas, even if coming from different clients, are then handled in such a way that they reach the replicas in the same order. The abstraction that provides this guarantee is called the total order broadcast primitive. Roughly speaking, this communication primitive ensures that messages broadcast within a group of processes are delivered in the same order, despite concurrency and failures.
---
paper_title: Byzantine Fault Detectors for Solving Consensus

paper_content:

Unreliable fault detectors can be defined in terms of completeness and accuracy properties and can be used to solve the consensus problem in asynchronous distributed systems that are subject to crash faults. We extend this result to asynchronous distributed systems that are subject to Byzantine faults. First, we define and categorize Byzantine faults. We then define two new completeness properties, eventual strong completeness and eventual weak completeness. We use these completeness properties and previously defined accuracy properties to define four new classes of unreliable Byzantine fault detectors. Next, we present an algorithm that uses a Byzantine fault detector to solve the consensus problem in an asynchronous distributed system of n processes in which the number k of Byzantine faults satisfies k ≤� (n − 1)/3� . We also give algorithms that implement a Byzantine fault detector in a model of partial synchrony. Finally, we prove the correctness of the consensus algorithm and analyze its complexity.
---
paper_title: Unreliable intrusion detection in distributed computations

paper_content:

Distributed coordination is difficult, especially when the system may suffer intrusions that corrupt some component processes. We introduce the abstraction of a failure detector that a process can use to (imperfectly) detect the corruption (Byzantine failure) of another process. In general, our failure detectors can be unreliable, both by reporting a correct process to be faulty or by reporting a faulty process to be correct. However, we show that if these detectors satisfy certain plausible properties, then the well known distributed consensus problem can be solved. We also present a randomized protocol using failure detectors that solves the consensus problem if either the requisite properties of failure detectors hold or if certain highly probable events eventually occur. This work can be viewed as a generalization of benign failure detectors popular in the distributed computing literature.
---
paper_title: Muteness Failure Detectors: Specification and Implementation

paper_content:

This paper extends the failures detector approach from crash-stop failures to muteness failures. Muteness failures are malicious failures in which a process stops sending algorithm messages, but might continue to send other messages, e.g., "I-am-alive" messages. The paper presents both the specification of a muteness failure detector, denoted by ⋄MA, and an implementation of ⋄MA in a partial synchrony model (there are bounds on message latency and clock skew, but these bounds are unknown and hold only after some point that is itself unknown). We show that, modulo a simple modification a consensus algorithm that has been designed in a crash-stop model with ⋄S, can be reused in the presence of muteness failures simply by replacing ⋄MA with ⋄S.
---
paper_title: Asynchronous implementation of failure detectors

paper_content:

Unreliable failure detectors introduced by Chandra and Toueg are abstract mechanisms that provide information on process failures. On the one hand, failure detectors allow to state the minimal requirements on process failures that allow to solve problems that cannot be solved in purely asynchronous systems. But, on the other hand, they cannot be implemented in such systems: their implementation requires that the underlying distributed system be enriched with additional assumptions. The usual failure detector implementations rely on additional synchrony assumptions (e.g., partial synchrony). This paper proposes a new look at the implementation of failure detectors and more specifically at Chandra-Toueg’s failure detectors. The proposed approach does not rely on synchrony assumptions (e.g., it allows the communication delays to always increase). It is based on a query-response mechanism and assumes that the query/response messages exchanged obey a pattern where the responses from some processes to a query arrive among the (n − f ) first ones (n being the total number of processes, f the maximum number of them that can crash, with 1 ≤ f< n). When we consider the particular case f =1 , and the implementation of a failure detector of the class denoted S (the weakest class that allows to solve the consensus problem), the additional assumption the underlying system has to satisfy boils down to a simple channel property, namely, there is eventually a pair of processes (pi ,p j) such that the channel connecting them is never the slowest among the channels connecting pi or pj to the other processes. A probabilistic analysis shows that this requirement is practically met in asynchronous distributed systems.
---
paper_title: Minimal Byzantine Fault Tolerance: Algorithm and Evaluation

paper_content:

This paper presents two asynchronous Byzantine faulttolerant state machine replication (BFT) algorithms that are minimal in several senses. First, they require only 2 f + 1 replicas, instead of the usual 3 f + 1. Second, the trusted service in which this reduction of replicas is based is arguably minimal, so it is simple to verify and implement (which is possible even using commercial trusted hardware). Third, in nice executions the two algorithms run in the minimum number of communication steps for nonspeculative and speculative algorithms, respectively 4 and 3 steps. Besides the obvious benefits in terms of cost, resilience and management complexity of having less replicas to tolerate a certain number of faults, our algorithms are simpler than previous ones (being closer to crash faulttolerant replication algorithms). The performance evaluation shows that, even with the trusted component access overhead, they can have better throughput than Castro and Liskov’s PBFT, and better latency in networks with nonnegligible communication delays. Comparing with the previous paper DI-TR-08-29 [49], this version presents a slight modifications of the algorithms, the full proof of their correctness and a new performance evaluation.
---
paper_title: Attested append-only memory: making adversaries stick to their word

paper_content:

Researchers have made great strides in improving the fault tolerance of both centralized and replicated systems against arbitrary (Byzantine) faults. However, there are hard limits to how much can be done with entirely untrusted components; for example, replicated state machines cannot tolerate more than a third of their replica population being Byzantine. In this paper, we investigate how minimal trusted abstractions can push through these hard limits in practical ways. We propose Attested Append-Only Memory (A2M), a trusted system facility that is small, easy to implement and easy to verify formally. A2M provides the programming abstraction of a trusted log, which leads to protocol designs immune to equivocation -- the ability of a faulty host to lie in different ways to different clients or servers -- which is a common source of Byzantine headaches. Using A2M, we improve upon the state of the art in Byzantine-fault tolerant replicated state machines, producing A2M-enabled protocols (variants of Castro and Liskov's PBFT) that remain correct (linearizable) and keep making progress (live) even when half the replicas are faulty, in contrast to the previous upper bound. We also present an A2M-enabled single-server shared storage protocol that guarantees linearizability despite server faults. We implement A2M and our protocols, evaluate them experimentally through micro- and macro-benchmarks, and argue that the improved fault tolerance is cost-effective for a broad range of uses, opening up new avenues for practical, more reliable services.
---
paper_title: The design of a COTS real-time distributed security kernel

paper_content:

This paper describes the design of a security kernel called TTCB, which has innovative features. Firstly, it is a distributed sub-system with its own secure network. Secondly, the TTCB is real-time, that is, a synchronous subsystem capable of timely behavior. These two characteristics together are uncommon in security kernels. Thirdly, the TTCB can be implemented using only COTS components. ::: ::: We discuss essentially three things in this paper: (1) The TTCB is a simple component providing a small set of basic secure services. It aims at building a new style of protocols to achieve intrusion tolerance, which for the most part execute in insecure, arbitrary failure environments, and resort to the TTCB only in crucial parts of their operation. (2) Besides, the TTCB is a synchronous device supplying functions that may be an enabler of a new generation of timed secure protocols, until now known to be fragile due to attacks on timing assumptions. (3) Finally, we present a design methodology that establishes our hybrid failure assumptions in a well-founded manner. It helps us to achieve a robust design, despite using exclusively COTS components, with the advantage of allowing the security kernel to be easily deployed on widely used platforms.
---
paper_title: Highly-Resilient Services for Critical Infrastructures

paper_content:

Modern society depends on several critical infrastructures like power, water, oil and gas generation and distribution. These infrastructures have evolved to become largely controlled by computers and interconnected by computer networks, which lets them exposed to the same types of threats as Internet systems. Therefore, research about mechanisms to improve the protection of these infrastructures is extremely important. Byzantine fault-tolerant (BFT) replication algorithms tackle this problem by allowing critical services, like storage and processing of monitoring data, to continue to operate correctly even if some of their components are compromised by malicious attackers. This paper proposes a novel BFT algorithm that requires fewer replicas, fewer communication steps and analytically seems to have better throughput and latency than others in literature. The main idea is to provide an efficient BFT algorithm suitable to WANs, to be applied in the construction of highly-resilient services for critical infrastructures, tolerating even the physical destruction of some servers.
---
paper_title: Travelling through wormholes: a new look at distributed systems models

paper_content:

The evolution of distributed computing and applications has put new challenges on models, architectures and systems. To name just one, 'reconciling uncertainty with predictability' is required by today's simultaneous pressure on increasing the quality of service of applications, and on degrading the assurance given by the infrastructure.This challenge can be mapped onto more than one facet, such as time or security or others. In this paper we explore the time facet, reviewing past and present of distributed systems models, and making the case for the use of hybrid (vs. homogeneous) models, as a key to overcoming some of the difficulties faced when asynchronous models (uncertainty) meet timing specifications (predictability). The Wormholes paradigm is described as the first experiment with hybrid distributed systems models.
---
paper_title: TrInc: Small Trusted Hardware for Large Distributed Systems

paper_content:

A simple yet remarkably powerful tool of selfish and malicious participants in a distributed system is "equivocation": making conflicting statements to others. We present TrInc, a small, trusted component that combats equivocation in large, distributed systems. Consisting fundamentally of only a non-decreasing counter and a key, TrInc provides a new primitive: unique, once-in-a-lifetime attestations. ::: ::: We show that TrInc is practical, versatile, and easily applicable to a wide range of distributed systems. Its deployment is viable because it is simple and because its fundamental components--a trusted counter and a key--are already deployed in many new personal computers today. We demonstrate TrInc's versatility with three detailed case studies: attested append-only memory (A2M), PeerReview, and BitTorrent. ::: ::: We have implemented TrInc and our three case studies using real, currently available trusted hardware. Our evaluation shows that TrInc eliminates most of the trusted storage needed to implement A2M, significantly reduces communication overhead in PeerReview, and solves an open incentives issue in BitTorrent. Microbenchmarks of our TrInc implementation indicate directions for the design of future trusted hardware.
---
paper_title: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols

paper_content:

The condition-based approach for consensus solvability consists of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes.This paper investigates Cf, the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that Cf is made up of a hierarchy of classes of conditions, Cf[d]. where d is a parameter (called degree of the condition), starting with d=min(n - f, f) and ending with d = 0, where Cf0=Cf. We prove that each one is strictly contained in the previous one: Cf[d] ⊂ Cf[d-1]. Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, C ∈ Cf[d], and requires at most (2n+1) ⌈log2(⌈(f - d)/2⌉+1)⌉ shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f - d) represents the "difficulty" of the class Cf[d]. An improvement of the protocol for the conditions in Cf[0] is also presented.
---
paper_title: Distributed agreement and its relation with error-correcting codes

paper_content:

The condition based approach identifies sets of input vectors, called conditions, for which it is possible to design a protocol solving a distributed problem despite process crashes. This paper investigates three related agreement problems, namely consensus, interactive consistency, and k-set agreement, in the context of the condition-based approach. In consensus, processes have to agree on one of the proposed values; in interactive consistency, they have to agree on the vector of proposed values; in k-set agreement, each process decides on one of the proposed values, and at most k different values can be decided on. For both consensus and interactive consistency, a direct correlation between these problems and error correcting codes is established. In particular, crash failures in distributed agreement problems correspond to erasure failures in error correcting codes, and Byzantine and value domain faults correspond to corruption errors. It is also shown that less restrictive codes can be used to solve k-set agreement, but without a necessity proof, which is still an open problem.
---
paper_title: Conditions on input vectors for consensus solvability in asynchronous distributed systems

paper_content:

This paper introduces and explores a new condition based approach to solve the consensus problem in asynchronous systems. The approach consists of identifying sets of input vectors, called conditions , for which it is possible to design a protocol solving consensus despite the occurrence of up to f process crashes. The first main result is a generic consensus protocol for the shared memory model. It always guarantees agreement, and also termination (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. Then, two particular realistic conditions are defined, and proved to be maximal. The second main result is a characterization of the conditions that allow to solve consensus. The consensus protocol works for any such condition. An efficient version of the protocol is then designed for the message passing model that works when f≥n/2 , and it is shown that no such protocol exists when f≥n/2 . It is also shown how the protocol's safety can be traded for its liveness.
---
paper_title: More Choices Allow More Faults: Set Consensus Problems In Totally Asynchronous Systems

paper_content:

Abstract We define the k -SET CONSENSUS PROBLEM as an extension of the CONSENSUS problem, where each processor decides on a single value such that the set of decided values in any run is of size at most k . We require the agreement condition that all values decided upon are initial values of some processor. We show that the problem has a simple ( k −1)-resilient protocol in a totally asynchronous system. In an attempt to come up with a matching lower bound on the number of failures, we study the uncertainty condition, which requires that there must be some initial configuration from which all possible input values can be decided. We prove using a combinatorial argument that any k -resilient protocol for the k -set agreement problem would satisfy the uncertainty condition, while this is not true for any ( k −1)-resilient protocol. This result seems to strengthen the conjecture that there is no k -resilient protocol for this problem. We prove this result for a restricted class of protocols. Our motivation for studying this problem is to test whether the number of choices allowed to the processors is related to the number of faults . We hope that this will provide intuition towards achieving better bounds for more practical problems that arise in distributed computing, e.g., the renaming problem. The larger goal is to characterize the boundary between possibility and impossibility in asynchronous systems given multiple faults.
---
paper_title: Randomized Intrusion-Tolerant Asynchronous Services

paper_content:

Randomized agreement protocols have been around for more than two decades. Often assumed to be inefficient due to their high expected communication and time complexities, they have remained largely overlooked by the community-at-large as a valid solution for the deployment of fault-tolerant distributed systems. This paper aims to demonstrate that randomization can be a very competitive approach even in hostile environments where arbitrary faults can occur. A stack of randomized intrusion-tolerant protocols is described and its performance evaluated under different faultloads. The stack provides a set of relevant services ranging from basic communication primitives up to atomic broadcast. The experimental evaluation shows that the protocols are efficient and no performance reduction is observed under certain Byzantine faults.
---
paper_title: Fast Byzantine Consensus

paper_content:

We present the first consensus protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication step, and number of processes for 2-step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case.
---
paper_title: Challenges in evaluating distributed algorithms

paper_content:

Theoretical evaluation of performance, availability, and reliability of distributed algorithms is always based on models and metrics that make some simplifying assumptions. Such assumptions are needed in order to have simple abstractions for reasoning about algorithms. However, such assumptions often lead to models, metrics, and analyses that fail to capture important aspects of actual system behavior. Using realistic system models and metrics is important, since distributed algorithms and systems are often designed to optimize over such metrics.
---
paper_title: Secure agreement protocols: reliable and atomic group multicast in rampart

paper_content:

Reliable and atomic group multicast have been proposed as fundamental communication paradigms to support secure distributed computing in systems in which processes may behave maliciously. These protocols enable messages to be multicast to a group of processes, while ensuring that all honest group members deliver the same messages and, in the case of atomic multicast, deliver these messages in the same order. We present new reliable and atomic group multicast protocols for asynchronous distributed systems. We also describe their implementation as part of Rampart, a toolkit for building high-integrity distributed services, i.e., services that remain correct and available despite the corruption of some component servers by an attacker. To our knowledge, Rampart is the first system to demonstrate reliable and atomic group multicast in asynchronous systems subject to process corruptions.
---
paper_title: Redundancy and Diversity in Security

paper_content:

Redundancy and diversity are commonly applied principles for fault tolerance against accidental faults. Their use in security, which is attracting increasing interest, is less general and less of an accepted principle. In particular, redundancy without diversity is often argued to be useless against systematic attack, and diversity to be of dubious value. This paper discusses their roles and limits, and to what extent lessons from research on their use for reliability can be applied to security, in areas such as intrusion detection. We take a probabilistic approach to the problem, and argue its validity for security. We then discuss the various roles of redundancy and diversity for security, and show that some basic insights from probabilistic modelling in reliability and safety indeed apply to examples of design for security. We discuss the factors affecting the efficacy of redundancy and diversity, the role of ”independence” between layers of defense, and some of the tra! de-offs facing designers.
---
paper_title: Consensus in Byzantine asynchronous systems

paper_content:

This paper presents a consensus protocol resilient to Byzantine failures. It uses signed and certified messages and is based on two underlying failure detection modules. The first is a muteness failure detection module of the class ♦M. The second is a reliable Byzantine behaviour detection module. More precisely, the first module detects processes that stop sending messages, while processes experiencing other non-correct behaviours (i.e., Byzantine) are detected by the second module. The protocol is resilient to F faulty processes, F ≤ min(⌊(n - 1)/2⌋, C) (where C is the maximum number of faulty processes that can be tolerated by the underlying certification service).The approach used to design the protocol is new. While usual Byzantine consensus protocols are based on failure detectors to detect processes that stop communicating, none of them use a module to detect their Byzantine behaviour (this detection is not isolated from the protocol and makes it difficult to understand and prove correct). In addition to this modular approach and to a consensus protocol for Byzantine systems, the paper presents a finite state automaton-based implementation of the Byzantine behaviour detection module. Finally, the modular approach followed in this paper can be used to solve other problems in asynchronous systems experiencing Byzantine failures.
---
paper_title: Asynchronous Byzantine consensus with 2f+1 processes

paper_content:

Byzantine consensus in asynchronous message-passing systems has been shown to require at least 3f + 1 processes to be solvable in several system models (e.g., with failure detectors, partial synchrony or randomization). Recently a couple of solutions to implement Byzantine fault-tolerant state-machine replication using only 2f + 1 replicas have appeared. This reduction from 3f + 1 to 2f + 1 is possible with a hybrid system model, i.e., by extending the system model with trusted/trustworthy components that constrain the power of faulty processes to have certain behaviors. Despite these important results, the problem of solving Byzantine consensus with only 2f + 1 processes is still far from being well understood. In this paper we present a methodology to transform crash consensus algorithms into Byzantine consensus algorithms with different characteristics, with the assistance of a reliable broadcast primitive that requires trusted/trustworthy components to be implemented. We exemplify the methodology with two algorithms, one that uses failure detectors and one that is randomized. We also define a new flavor of consensus and use it to solve atomic broadcast, showing the practical interest of the transformations.
---
paper_title: Designing Modular and Redundant Cyber Architectures for Process Control: Lessons learned

paper_content:

An architecture was recently proposed to protect the power grid, in the context of a European project. The design of the architecture, guided by an analysis of the evolution of critical information infrastructures, tried to be as generic as possible, with a view of possibly serving as a reference cyber architecture for process control infrastructures.The need for a new architecture is explained by the fact that cyber architectures for process control, despite being basically physical processes controlled by computers interconnected by networks, exhibit a potentially huge cost of failure in socio-economic terms, thus bringing extremely demanding requirements, which have not been previously found together in a same class of computer-based systems.In this paper we wish to report the lessons learned in the development, analysis and evaluation of the proposed cyber architecture for process control.
---
paper_title: How practical are intrusion-tolerant distributed systems?

paper_content:

Building secure, inviolable systems using traditional mechanisms is becoming increasingly an unattainable goal. The recognition of this fact has fostered the interest in alternative approaches to security such as intrusion tolerance, which applies fault tolerance concepts and techniques to security problems. Albeit this area is quite promising, intrusion-tolerant distributed systems typically rely on the assumption that the system components fail or are compromised independently. This is a strong assumption that has been repeatedly questioned. In this paper we discuss how this assumption can be implemented in practice using diversity of system components. We present a taxonomy of axes of diversity and discuss how they provide failure independence. Furthermore, we provide a practical example of an intrusion-tolerant system built using diversity.
---
paper_title: An asynchronous [(n - 1)/3]-resilient consensus protocol

paper_content:

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 n /3, thus matching the lower bound on the number of correct processes necessary for consensus. The protocol restricts the behaviour of the malicious processes to that of merely fail-stop processes, which makes it interesting in other contexts.
---
paper_title: From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures

paper_content:

This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical distributed systems: multi-valued consensus, vector consensus and atomic broadcast. These protocols are designed as successive transformations from one to another. The first protocol, multi-valued consensus, is implemented on top of a randomized binary consensus and a reliable broadcast protocol. The protocols share a set of important structural properties. First, they do not use digital signatures constructed with public-key cryptography, a well-known performance bottleneck in this kind of protocols. Second, they are time-free, i.e. they make no synchrony assumptions, since these assumptions are often vulnerable to subtle but effective attacks. Third, they are completely decentralized, thus avoiding the cost of detecting corrupt leaders. Fourth, they have optimal resilience, i.e. they tolerate the failure of f = ⌊(n-1)/3⌋ out of a total of n processes. In terms of time complexity, the multi-valued consensus protocol terminates in a constant expected number of rounds, while the vector consensus and atomic broadcast protocols have O(f) complexity. The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures. A similar proof is given for the equivalence between multi-valued consensus and vector consensus. These two results have theoretical relevance since they show once more that consensus is a fundamental problem in distributed systems.
---
paper_title: Consensus in the presence of partial synchrony

paper_content:

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound P on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and P exist. In one version of partial synchrony, fixed bounds Δ and P exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and P. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T , and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
---
paper_title: Secure and efficient asynchronous broadcast protocols (extended abstract

paper_content:

Broadcast protocols are a fundamental building block for implementing replication in fault-tolerant distributed systems. This paper addresses secure service replication in an asynchronous environment with a static set of servers, where a malicious adversary may corrupt up to a threshold of servers and controls the network. We develop a formal model using concepts from modern cryptography, give modular definitions for several broadcast problems, including reliable, atomic, and secure causal broadcast, and present protocols implementing them. Reliable broadcast is a basic primitive, also known as the Byzantine generals problem, providing agreement on a delivered message. Atomic broadcast imposes additionally a total order on all delivered messages. We present a randomized atomic broadcast protocol based on a new, efficient multi-valued asynchronous Byzantine agreement primitive with an external validity condition. Apparently, no such efficient asynchronous atomic broadcast protocol maintaining liveness and safety in the Byzantine model has appeared previously in the literature. Secure causal broadcast extends atomic broadcast by encryption to guarantee a causal order among the delivered messages. Our protocols use threshold cryptography for signatures, encryption, and coin-tossing.
---
paper_title: Extending binary Byzantine agreement to multivalued Byzantine agreement

paper_content:

Abstract A binary Byzantine agreement algorithm can be extended to produce a multivalued Byzantine agreement algorithm. The resulting multivalued algorithm is cheaper than previously published algorithms when the cost of transmitting values from the multivalued domain is significant.
---
paper_title: Randomized Byzantine Agreements

paper_content:

Randomized algorithms for reaching Byzantine Agreement were recently proposed in [Rabi83]. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes n and the number of faulty processes t . The algorithms in [Rabi83] tolerate up to [( n -1)/10] faulty processes in asynchronous systems, and up to [( n -1)/4] faulty processes in synchronous systems. In this paper, using the same computation model as in [Rabi83], we describe algorithms that overcome up to [( n -1)/3] faulty processes in asynchronous systems, and up to [( n -1)/2] faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of n and t , but the communication complexity is higher than in [Rabi83]. It is also shown that no Byzantine Agreement algorithm can overcome more than [( n -1)/3] faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.
---
paper_title: Implementing fault-tolerant services using the state machine approach: a tutorial

paper_content:

The state machine approach is a general method for implementing fault-tolerant services in distributed systems. This paper reviews the approach and describes protocols for two different failure models—Byzantine and fail stop. Systems reconfiguration techniques for removing faulty components and integrating repaired components are also discussed.
---
paper_title: From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures

paper_content:

This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical distributed systems: multi-valued consensus, vector consensus and atomic broadcast. These protocols are designed as successive transformations from one to another. The first protocol, multi-valued consensus, is implemented on top of a randomized binary consensus and a reliable broadcast protocol. The protocols share a set of important structural properties. First, they do not use digital signatures constructed with public-key cryptography, a well-known performance bottleneck in this kind of protocols. Second, they are time-free, i.e. they make no synchrony assumptions, since these assumptions are often vulnerable to subtle but effective attacks. Third, they are completely decentralized, thus avoiding the cost of detecting corrupt leaders. Fourth, they have optimal resilience, i.e. they tolerate the failure of f = ⌊(n-1)/3⌋ out of a total of n processes. In terms of time complexity, the multi-valued consensus protocol terminates in a constant expected number of rounds, while the vector consensus and atomic broadcast protocols have O(f) complexity. The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures. A similar proof is given for the equivalence between multi-valued consensus and vector consensus. These two results have theoretical relevance since they show once more that consensus is a fundamental problem in distributed systems.
---
paper_title: Worm-IT – A Wormhole-based Intrusion-Tolerant Group Communication System

paper_content:

This paper presents Worm-IT, a new intrusion-tolerant group communication system with a membership service and a view-synchronous atomic multicast primitive. The system is intrusion-tolerant in the sense that it behaves correctly even if some nodes are corrupted and become malicious. It is based on a novel approach that enhances the environment with a special secure distributed component used by the protocols to execute securely a few crucial operations. Using this approach, we manage to bring together two important features: Worm-IT tolerates the maximum number of malicious members possible; it does not have to detect the failure of primary-members, a problem in previous intrusion-tolerant group communication systems.
---
paper_title: The Generic Consensus Service

paper_content:

This paper describes a modular approach for the construction of fault-tolerant agreement protocols. The approach is based on a generic consensus service. Fault-tolerant agreement protocols are built using a client-server interaction, where the clients are the processes that must solve the agreement problem and the servers implement the consensus service. This service is accessed through a generic consensus filter, customized for each specific agreement problem. We illustrate our approach on the construction of various fault-tolerant agreement protocols, such as nonblocking atomic commitment, group membership, view synchronous communication, and total order multicast. Through a systematic reduction to consensus, we provide a simple way to solve agreement problems. In addition to its modularity, our approach enables efficient implementations of agreement protocols and precise characterization of the assumptions underlying their liveness and safety properties.
---

Title: Byzantine consensus in asynchronous message-passing systems: a survey

Section 1: Introduction
Description 1: Provide an overview of the paper, highlighting the importance of Byzantine consensus in distributed systems and the scope of the survey.

Section 2: Byzantine consensus definitions
Description 2: Define the consensus problem and its variations as discussed in the literature, such as binary consensus and multi-valued consensus.

Section 3: FLP Impossibility
Description 3: Explain the FLP impossibility result, its implications, and alternative proofs.

Section 4: Circumventing FLP
Description 4: Introduce the techniques used to circumvent FLP and the algorithms that implement these techniques.

Section 5: Sacrificing determinism
Description 5: Describe the use of randomization to create probabilistic algorithms that circumvent FLP.

Section 6: Adding time to the model
Description 6: Discuss the notion of partial synchrony and how adding timing assumptions can help solve consensus.

Section 7: Augmenting the system model with an oracle
Description 7: Explain the use of failure detectors and other oracles to assist in solving consensus.

Section 8: Hybridisation and wormholes
Description 8: Explore the concept of wormholes and how they provide enhanced properties to otherwise uncertain systems.

Section 9: Modifying the problem
Description 9: Describe how FLP can be circumvented by modifying the definition of the consensus problem.

Section 10: Evaluating consensus algorithms
Description 10: Discuss the metrics used to evaluate the performance, scalability, and resilience of Byzantine consensus algorithms.

Section 11: Related and equivalent problems
Description 11: Examine other distributed systems problems equivalent to consensus and the transformations between them.

Section 12: Conclusions
Description 12: Summarize the survey, emphasizing the significance and future trends of Byzantine consensus in distributed systems.