Maurice Herlihy

TCS Journal 2026 Journal Article

Byzantine reliable broadcast and tendermint consensus with trusted components

• Yackolley Amoussou-Guenou
• Lionel Beltrando
• Maurice Herlihy
• Maria Potop-Butucaru

• we study Byzantine Reliable Broadcast when processes are equipped with trusted components, special software or hardware designed to prevent equivocation. • we show that, despite common belief, when each process is equipped with a trusted component, Bracha’s algorithm still needs n ≥ 3 t + 1. • we present a novel algorithm that implements Byzantine Reliable Asynchronous Broadcast with n ≥ 2 t + 1. • we present TenderTee, a transformation of the Tendermint consensus algorithm by using trusted component, giving better Byzantine resilience. Tendertee works with n ≥ 2 t + 1, where Tendermint needed n = 3 t + 1. Byzantine Reliable Broadcast is one of the most popular communication primitives in distributed systems. Byzantine reliable broadcast ensures that processes agree to deliver a message from an initiator, even if some processes (possibly including the initiator) are Byzantine. In asynchronous settings, it is known since the prominent work of Bracha ( Information and Computation, 1987 ) that Byzantine reliable broadcast can be implemented deterministically if the total number of processes, denoted by n, satisfies n ≥ 3 t + 1 where t is an upper bound on the number of Byzantine processes. Here, we study both Byzantine Reliable Broadcast and Consensus problems when processes are equipped with trusted components, special software or hardware designed to prevent equivocation. Our contribution is threefold. First, we show that, despite common belief, when each process is equipped with a trusted component, Bracha’s algorithm still needs n ≥ 3 t + 1. Second, we present a novel algorithm that uses a single trusted component (at the initiator) that implements Byzantine Reliable Asynchronous Broadcast with n ≥ 2 t + 1. Lastly, building on our broadcast algorithm, we present TenderTee, a transformation of the Tendermint consensus algorithm by using trusted component, giving better Byzantine resilience. Tendertee works with n ≥ 2 t + 1, where Tendermint needed n = 3 t + 1.

TCS Journal 2023 Journal Article

Flexible scheduling of transactional memory on trees

• Costas Busch
• Bogdan S. Chlebus
• Maurice Herlihy
• Miroslav Popovic
• Pavan Poudel
• Gokarna Sharma

We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a static network with the topology of a tree. Contrary to previous approaches, we allow the flexibility for both transactions and their requested objects to move simultaneously among the nodes in the tree. Given a batch of transactions and shared objects, the goal is to produce a schedule of executing the transactions that minimizes the cost of moving the transactions and the objects in the tree. We consider both techniques for accessing a remote object with respect to a transaction movement. In the first technique, instead of moving, transactions send control messages to remote nodes where the requested objects are gathered. In the second technique, the transactions migrate to the remote nodes where the objects are gathered to access them. When all the transactions use a single object, we give an offline algorithm that produces optimal schedules for both techniques. For the general case of multiple objects per transaction, in the first technique, we obtain a schedule with a constant-factor approximation of optimal. In the second technique, with transactions migrating, we give a k factor approximation where k is the maximum number of objects per transaction.

I&C Journal 2022 Journal Article

Clairvoyant state machine replication

• Rida Bazzi
• Maurice Herlihy

We consider the state machine replication problem in semi-synchronous systems subject to Byzantine server failures. We propose a new solution to the problem in the form of a protocol for the generalized consensus problem. The protocol solves the consensus problem in a setting in which information about conflicts between transactions is available (such information can be in the form of transaction read and write sets). Unlike most prior proposals (for generalized or classical consensus), which use a leader to order transactions, this protocol is leaderless, and relies on non-skipping timestamps for transaction ordering. Being leaderless, the protocol does not need to pause for leader elections. The use of non-skipping timestamps permits servers to commit transactions as soon as they know that no conflicting transaction can be ordered earlier. For n servers of which f may be faulty, this protocol requires n > 4 f.

I&C Journal 2022 Journal Article

Load balanced distributed directories

• Shishir Rai
• Gokarna Sharma
• Costas Busch
• Maurice Herlihy

We present LB-Spiral, a novel distributed directory protocol for shared objects, suitable for large-scale distributed shared memory systems. Each shared object has an owner node that can modify its value. The ownership may change by moving the object from one node to another in response to move requests. The value of an object can be read by other nodes with lookup requests. The distinctive feature of LB-Spiral is that it balances the processing load on nodes in addition to minimizing the communication cost in general network topologies. In contrast, the existing distributed directory protocols for general network topologies only minimize the communication cost. In particular, LB-Spiral achieves poly-log approximation for both load and communication cost in general networks with respect to the problem parameters. Simulation results show that the established theoretical results translate well in practice.

TCS Journal 2017 Journal Article

From wait-free to arbitrary concurrent solo executions in colorless distributed computing

• Maurice Herlihy
• Sergio Rajsbaum
• Michel Raynal
• Julien Stainer

In an asynchronous distributed system where any number of processes may crash, a process may have to run solo, computing its local output without receiving any information from other processes. In the basic shared memory system where the processes communicate through atomic read/write registers, at most one process may run solo. This paper introduces the family of d-solo models, where d-processes may concurrently run solo, 1 ≤ d ≤ n (the 1-solo model is the basic read/write model). The paper then studies distributed colorless computations in the d-solo models, where process ids are not used, either in task specifications or during computation. It presents a characterization of the colorless tasks that can be solved in each d-solo model. Colorless tasks include consensus, set agreement and many other previously studied tasks. It shows that colorless algorithms have limited computational power for solving tasks, only when d > 1. When d = 1, colorless algorithms can solve the same tasks as algorithms that may use ids. It is well-known that, while consensus is not wait-free solvable in a model where at most one process may run solo, ϵ-approximate agreement is solvable. In a d-solo model, the fundamental solvable task is ( d, ϵ ) -solo approximate agreement, a generalization of ϵ-approximate agreement. Indeed, ( d, ϵ ) -solo approximate agreement can be solved in the d-solo model, but not in the ( d + 1 ) -solo model. Finally, the paper studies a link between the solvability of d-set agreement and ( d, ϵ ) -solo approximate agreement in asynchronous wait-free message-passing systems, which provides an insight on the “maximal partitioning” allowed to solve an approximate agreement task.

STOC Conference 2014 Conference Paper

Distributed computability in Byzantine asynchronous systems

• Hammurabi Mendes
• Christine Tasson
• Maurice Herlihy

In this work, we extend the topology-based approach for characterizing computability in asynchronous crash-failure distributed systems to asynchronous Byzantine systems. We give the first theorem with necessary and sufficient conditions to solve arbitrary tasks in asynchronous Byzantine systems where an adversary chooses faulty processes. For colorless tasks, an important subclass of distributed problems, the general result reduces to an elegant model that effectively captures the relation between the number of processes, the number of failures, as well as the topological structure of the task's simplicial complexes.

STOC Conference 2013 Conference Paper

Multidimensional approximate agreement in Byzantine asynchronous systems

• Hammurabi Mendes
• Maurice Herlihy

The problem of ε-approximate agreement in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values that lie in R m , for m ≥ 1, and present an optimal protocol in regard to fault tolerance. Our scenario is the following. Processes start with values in R m , for m ≥ 1, and communicate via message-passing. The system is asynchronous : there is no upper bound on processes' relative speeds or on message delay. Some faulty processes can display arbitrarily malicious (i.e. Byzantine) behavior. Non-faulty processes must decide on values that are: (1) in R m ; (2) within distance ε of each other; and (3) in the convex hull of the non-faulty processes' inputs. We give an algorithm with a matching lower bound on fault tolerance: we require n > t(m+2), where n is the number of processes, t is the number of Byzantine processes, and input and output values reside in R m . Non-faulty processes send O(n 2 d log(m/ε max{δ(d): 1 ≤ d ≤ m})) messages in total, where δ(d) is the range of non-faulty inputs projected at coordinate d. The Byzantine processes do not affect the algorithm's running time.

TCS Journal 2013 Journal Article

Power and limits of distributed computing shared memory models

• Maurice Herlihy
• Sergio Rajsbaum
• Michel Raynal

What can and cannot be computed in a distributed system is a complex function of the system’s communication model, timing model, and failure model. Considering a canonical distributed system model, where processes execute asynchronously, communicate by reading and writing shared memory, and fail by crashing, this paper surveys important results about computability, and explains the fundamental role that topology plays in the distributed computability theory. The paper also considers different types of additional assumptions that allow impossibility results to be circumvented. These assumptions are known under the names failure detectors and adversaries. Finally, it presents a powerful simulation technique (known under the name BG simulation), which allows to show that, from a computability point of view, t -resilience is not different from wait-freedom. When pieced together, the aim of all the concepts, notions, models, and algorithms presented in the paper, is to provide the reader with a synthetic view of important results on the distributed asynchronous read/write shared-memory model, its power and its limits.

TCS Journal 2009 Journal Article

A topological treatment of early-deciding set-agreement

• Rachid Guerraoui
• Maurice Herlihy
• Bastian Pochon

The k -set-agreement problem consists for a set of n processes to agree on less than k among n possibly different values, each initially known to only one process. The problem is at the heart of distributed computing and generalizes the celebrated consensus problem. This paper considers the k -set-agreement problem in a synchronous message passing distributed system where up to t processes can fail by crashing. We determine the number of communication rounds needed for all correct processes to reach a decision in a given run, as a function of the degree of coordination k and the number of processes that actually fail in the run, f ≤ t. We prove that, for any integer 1 ≤ k < n, for any set-agreement protocol, for any integer 0 ≤ f ≤ t, not all correct processes can decide within ⌊ f / k ⌋ + 1 rounds, in any run with at most f process crashes. More specifically, we prove a lower bound of min ( ⌊ f / k ⌋ + 2, ⌊ t / k ⌋ + 1 ) rounds for early-deciding set-agreement. This bound is tight because there is a set-agreement protocol that matches it, and the bound generalizes both the min ( f + 2, t + 1 ) bound previously obtained for early-deciding consensus and the t + 1 bound previously obtained for the worst-case complexity of set-agreement.

TCS Journal 2003 Journal Article

A classification of wait-free loop agreement tasks

• Maurice Herlihy
• Sergio Rajsbaum

Loop agreement is a family of wait-free tasks that includes instances of set agreement and approximate agreement tasks. A task G implements task F if one can construct a solution to F from a solution to G, possibly followed by access to a read/write memory. Loop agreement tasks form a lattice under this notion of implementation. This paper presents a classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a finitely presented group G and a distinguished element g in G. This signature characterizes the task's power to implement other tasks. If F and G are loop agreement tasks with respective signatures 〈F, f〉 and 〈G, g〉, then F implements G if and only if there exists a group homomorphism h: F→G carrying f to g.

TCS Journal 2002 Journal Article

Threshold counters with increments and decrements

• Costas Busch
• Neophytos Demetriou
• Maurice Herlihy
• Marios Mavronicolas

A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value ⌊v/w⌋, where v is the current counter value and w is a fixed constant. Thus, the Read operation returns the “approximate” value of the counter to within the constant w. Threshold counters have many potential uses, including software barrier synchronization. Threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. In this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a Decrement operation that changes the counter value from v to v−1.

STOC Conference 2000 Conference Paper

Hard-Potato routing

• Costas Busch
• Maurice Herlihy
• Roger Wattenhofer

FOCS Conference 2000 Conference Paper

On the Existence of Booster Types

• Maurice Herlihy
• Eric Ruppert

A data type's consensus number measures its power in asynchronous concurrent models of computation. We characterize the circumstances under which types of high consensus number can be constructed from types with lower consensus numbers, a process called boosting. In settings where boosting is impossible, we can reason about the synchronization power of objects in isolation. We give a new and simple topological condition, called /spl kappa/-solo-connectivity sufficient to ensure that one-shot types cannot be boosted to consensus number /spl kappa/. The booster type need not be one-shot; it can be arbitrary. We also show that, for /spl kappa/>2, any type that is not /spl kappa/-solo-connected can be boosted to consensus number /spl kappa/. For types that can be boosted, we establish an upper bound on the amount the consensus number can be increased. For finite types, these properties and bounds are computable. For deterministic one-shot types, the /spl kappa/-solo-connectivity property also exactly characterizes the types that have consensus number less than /spl kappa/.

SODA Conference 2000 Conference Paper

Randomized greedy hot-potato routing

• Costas Busch
• Maurice Herlihy
• Roger Wattenhofer

MFCS Conference 1999 Conference Paper

New Perspectives in Distributed Computing

• Maurice Herlihy
• Sergio Rajsbaum

Abstract This is an informal introduction to recent developments in the theory of distributed computing, showing how notions from combinatorial and algebraic topology can be used to capture essential aspects of distributed computing.

TCS Journal 1999 Journal Article

Wait-free implementations in message-passing systems

• Soma Chaudhuri
• Maurice Herlihy
• Mark R. Tuttle

We study the round complexity of problems in a synchronous, message-passing system with crash failures. We show that if processors start in order-equivalent states, then a logarithmic number of rounds is both necessary and sufficient for them to reach order-inequivalent states. These upper and lower bounds are significant because they establish a complexity threshold below which no nontrivial problem can be solved, but at which certain nontrivial problems do have solutions. This logarithmic lower bound implies a matching lower bound for a variety of decision tasks and concurrent object implementations. In particular, we examine two nontrivial problems for which this lower bound is tight: the strong renaming task, and a wait-free increment register implementation. For each problem, we present a nontrivial algorithm that halts in O(log c) rounds, where c is the number of participating processors.

STOC Conference 1997 Conference Paper

The Decidability of Distributed Decision Tasks (Extended Abstract)

• Maurice Herlihy
• Sergio Rajsbaum

STOC Conference 1994 Conference Paper

A simple constructive computability theorem for wait-free computation

• Maurice Herlihy
• Nir Shavit

FOCS Conference 1993 Conference Paper

A Tight Lower Bound for k-Set Agreement

• Soma Chaudhuri
• Maurice Herlihy
• Nancy A. Lynch
• Mark R. Tuttle

We prove tight bounds on the time needed to solve k-set agreement, a natural generalization of consensus. We analyze this problem in a synchronous, message-passing model where processors fail by crashing. We prove a lower bound of [f/k]+1 rounds of communication for solutions to k-set agreement that tolerate f failures. This bound is tight, and shows that there is an inherent tradeoff between the running time, the degree of coordination required, and the number of faults tolerated, even in idealized models like the synchronous model. The proof of this result is interesting because it is a geometric combination of other well-known proof techniques. >

STOC Conference 1993 Conference Paper

Contention in shared memory algorithms

• Cynthia Dwork
• Maurice Herlihy
• Orli Waarts

STOC Conference 1993 Conference Paper

The asynchronous computability theorem for t-resilient tasks

• Maurice Herlihy
• Nir Shavit

STOC Conference 1991 Conference Paper

Counting Networks and Multi-Processor Coordination

• James Aspnes
• Maurice Herlihy
• Nir Shavit

FOCS Conference 1991 Conference Paper

Low Contention Linearizable Counting

• Maurice Herlihy
• Nir Shavit
• Orli Waarts

The linearizable counting problem requires asynchronous concurrent processes to assign themselves successive values so that the order of the values assigned reflects the real-time order in which they were requested. It is shown that the problem can be solved without funneling all processes through a common memory location. Two new constructions for linearizable counting networks, data structures that solve the linearizable counting problem, are given. The first construction is nonblocking: some process takes a value after O(n) network gates have been traversed. The second construction is wait-free: it guarantees that each process takes a value after it traverses O(wn) gates, where w is a parameter affecting contention. It is shown that in any nonblocking or wait-free linearizable counting network, processes must traverse an average of Omega (n) gates, and so the constructions are close to optimal. A simpler and more efficient network is constructed by giving up the robustness requirements and allowing processes to wait for one another. >