Search

We ask to what extent processes communicating through shared memory can extract randomness from their underlying scheduler, e.g., to generate random numbers for cryptographic applications. We introduce the quantitative notions of entropy rate and information capacity of a distributed algorithm. Whilst the entropy rate measures the Shannon information that may pass from a given scheduler to the processes executing the algorithm, the information capacity measures the optimal entropy rate over all possible schedulers. We present a general method for computing these quantities by classifying distributed algorithms according to their pattern of shared memory accesses. We then address the issue of effectively extracting, online, the information produced by the scheduler into a meaningful format at every process. We present Duez, an algorithm solving this problem with an optimal memory consumption. Putting these principles into practice, we introduce Co-RNG, a random number generator that leverages the unpredictability of modern processors state. The power of Co-RNG comes from its simplicity. No specialized hardware is required: two concurrent threads actively perform successive reads and writes to shared memory locations. Another thread collects the sequences of values read by these two threads and seeks to reconstruct the interleaving of read and write operations. The resulting (Markovian) interaction scheme is then used to produce random bits. This simplicity yields a transparent behavior. If the hardware exhibits enough entropy, then Co-RNG efficiently extracts random numbers from it. We successfully experimented Co-RNG on various idle as well as loaded platforms, from laptops and desktops featuring Intel Core processors, to servers with Intel Xeon and AMD Opteron. Co-RNG passes all state-of-the-art random number generator statistical test suites while being faster than current I/O sampling based methods by 2–3 orders of magnitude.

This paper is on the construction and use of a shared memory abstraction on top of an asynchronous message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. These registers enable Byzantine tolerance by recording the whole history of values written to each one of them. A distributed algorithm building such a shared memory abstraction is first presented. This algorithm assumes t n / 3 , which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed objects built on top of this read/write shared memory abstraction, which cope with Byzantine processes. As illustrated by these objects, the proposed shared memory abstraction is motivated by the fact that, for a lot of problems, algorithms are simpler to design and prove correct in a shared memory system than in a message-passing system.

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.

When considering n-process asynchronous systems, where up to t processes can fail, and communication is by read/write registers or reliable message-passing, are (from a computability point of view) Byzantine failures “different” from crash failures? This is the question addressed in this paper, which shows that the answer is “no” for systems where \(t