A new book entitled “Concurrent Crash-Prone Shared Memory Systems: A Few Theoretical Notions” by Michel Raynal has just been published in the collection “Theoretical Notions Synthesis Lectures
on Distributed Computing Theory” published par Morgan & Claypool.
Abstract:
Theory is what remains true when technology is changing. So, it is important to know and
master the basic concepts and the theoretical tools that underlie the design of the systems we
are using today and the systems we will use tomorrow. This means that, given a computing
model, we need to know what can be done and what cannot be done in that model. Considering
systems built on top of an asynchronous read/write shared memory prone to process crashes,
this book presents and develops the fundamental notions that are universal constructions,
consensus numbers, distributed recursivity, power of the BG simulation, and what can be done
when one has to cope with process anonymity and/or memory anonymity. Numerous distributed
algorithms are presented, the aim of which being to help the reader better understand the
power and the subtleties of the notions that are presented. In addition, the reader can appreciate
the simplicity and beauty of some of these algorithms.
Keywords:
Abortable object, agreement, anonymous memory, anonymous process, asynchrony,
atomic operation, BG simulation, branching time, concurrent object, consensus,
consensus hierarchy, crash failure, deterministic object, distributed algorithm, distributed
computability, distributed task, help mechanism, linear time, memory location,
non-blocking, obstruction-freedom, progress condition, read/write register,recursion,
reduction, renaming, shared memory, write-snapshot, sequential specification, k -set agreement,
k -simultaneous consensus, speculative execution, universal construction, wait-freedom. recursion, reduction, renaming
