We define and show how to implement SWMR registers that provide properties of unforgeable digital signatures—without actually using such signatures—in systems with Byzantine processes. More precisely, we first define SWMR verifiable registers. Intuitively, processes can use these registers to write values as if they are "signed", such that these "signed values" can be "verified" by any process and "relayed" to any process. We give a signature-free implementation of such registers from plain SWMR registers in systems with n > 3f processes, f of which can be Byzantine. We also give a signature-free implementation of SWMR sticky registers from SWMR registers in systems with n > 3f processes. Once the writer p writes a value υ into a SWMR sticky register R, the register never changes its value. Note that the value υ can be considered "signed" by p: once p writes υ in R, p cannot change the value in R or deny that it wrote υ in R, and every reader can verify that p wrote υ just by reading R. This holds even if the writer p of R is Byzantine. We prove that our implementations are optimal in the number of Byzantine processes they can tolerate. Since SWMR registers can be implemented in message-passing systems with Byzantine processes and n > 3f [11], the results in this paper also show that one can implement verifiable registers and sticky registers in such systems.

The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributed computing. Since Lamport’s pioneering work [Leslie Lamport, 1986], this problem has been extensively studied in the context of asynchronous processes with crash failures. In this paper, we investigate this problem in the context of Byzantine process failures, with and without process signatures. In particular, we first show a strong impossibility result, namely, that there is no wait-free linearizable implementation of a 1-writer n-reader register from atomic 1-writer (n-1)-reader registers. In fact, this impossibility result holds even if all the processes except the writer are given atomic 1-writer n-reader registers, and even if we assume that the writer can only crash and at most one reader is subject to Byzantine failures. In light of this impossibility result, we give two register implementations. The first one implements a 1-writer n-reader register from atomic 1-writer 1-reader registers. This implementation is linearizable (under any combination of Byzantine process failures), but it is wait-free only under the assumption that the writer is correct or no reader is Byzantine - thus matching the impossibility result. The second implementation assumes process signatures; it is wait-free and linearizable under any number and combination of Byzantine process failures.

Motivated by recent distributed systems technology, Aguilera et al. introduced a hybrid model of distributed computing, called the message-and-memory model or m&m model for short. In this model, processes can communicate by message passing and also by accessing some shared memory (e.g., through some RDMA connections). We first consider the basic problem of implementing an atomic single-writer multi-reader (SWMR) register shared by all the processes in m&m systems. Specifically, we give an algorithm that implements such a register in m&m systems and show that it is optimal in the number of process crashes that it tolerates. This generalizes the well-known ABD implementation of an atomic SWMR register in a pure message-passing system. We then combine our register implementation for m&m systems with a randomized consensus algorithm of Aspnes and Herlihy, and obtain a randomized consensus algorithm for m&m systems that is also optimal in the number of process crashes that it can tolerate. Finally, we determine the minimum number of RDMA connections that is sufficient to implement a SWMR register, or solve randomized consensus, in an m&m system with t process crashes, for any given t .

It is well-known that, for deterministic algorithms, linearizable objects can be used as if they were atomic objects. As pointed out by Golab, Higham, and Woelfel, however, a randomized algorithm that works with atomic objects may lose some of its properties if we replace the atomic objects that it uses with objects that are only linearizable. It was not known whether the properties that can be lost include the all-important property of termination (with probability 1). In this paper, we first show that a randomized algorithm can indeed lose its termination property if we replace the atomic registers that it uses with linearizable ones.

Motivated by recent distributed systems technology, Aguilera et al. introduced a hybrid model of distributed computing, called message-and-memory model or m&m model for short [Marcos K. Aguilera et al., 2018]. In this model, processes can communicate by message passing and also by accessing some shared memory. We consider the basic problem of implementing an atomic single-writer multi-reader (SWMR) register shared by all the processes in m&m systems. Specifically, we give an algorithm that implements such a register in m&m systems and show that it is optimal in the number of process crashes that it can tolerate. This generalizes the well-known implementation of an atomic SWMR register in a pure message-passing system [Attiya et al., 1995].