Impossibility”), through the following
ingenious technique to implement it.
Whenever several processes (not necessarily known a priori, hence the name
of “dynamic system”) want to concurrently append a block, they participate
in a lottery. Each process selects a random number (by solving cryptographic
puzzles) between 0 and some large integer K, and the one that gets a number
smaller than k << K, wins, and has the
right to append its desired block.
The implementation details of the
lottery (by a procedure called proof of
work) are not important for this article; what is important here is that with
high probability only one wins (and selected at random). However, from time
to time, more than one process wins,
and a fork happens, with more than
one block being appended at the end
of the blockchain. Only one branch
eventually pervades (in Bitcoin this is
achieved by always appending to the
longest branch). This introduces a new
interesting idea into the paradigm of
mastering concurrency through sequential thinking: a trade-off between
faster state machine replication, and
temporary loss of consistency. In other
words, the x operations at the very end
of the blockchain, for some constant
x (which depends on the assumptions
about the environment) cannot yet be
The Limits of the Approach
It is intuitively clear, and it has been
formally proved, that linearizability or
even serializability may be costly. Re-
cent papers in the context of shared
memory programming, argue that it is
often possible to improve performance
of concurrent data structures by relax-
ing their semantics.
9 In the context
of distributed systems, eventual con-
sistency is widely deployed to achieve
high availability by guaranteeing that
if no new updates are made to a given
data item, eventually all accesses to
that item will return the last updated
value (despite its name is not techni-
cally a consistency condition.
3). In the
case of distributed ledgers, we have
seen the benefit that can be gained by
relaxing the sequential approach to
mastering concurrency: branches at
the end of the blockchain (such as Bit-
coin) temporarily violate a consistent
view of the ledger. Still, blockchains
suffer from a performance bottleneck
due to the requirement of ordering all
transactions in a single list, which has
prompted the exploration of partially
ordered ledgers, based on directed acy-
clic graphs such as those of Tangle or
The CAP Theorem formalizes a fun-
damental limitation of the approach
of mastering concurrency through se-
quential reasoning—at most, two of the
following three properties are achiev-
able: consistency, availability, partition
17 This may give an intuition
of why distributed ledgers implemen-
tations have temporary forks. An alter-
native is a cost in availability and post-
pone the property that every non-failing
participant returns a response for all
operations in a reasonable amount of
time. We have already seen in the ABD
algorithm that the system continues to
function and upholds its consistency
guarantees, provided that only a minor-
ity of processes may fail.
Finally, another fundamental limita-
tion to the approach of mastering con-
currency through sequential reasoning
is that not all concurrent problems of
interest have sequential specifications.
Many examples are discussed in Casta-
ñeda et al.,
10 where a generalization of
linearizability to arbitrary concurrent
specifications is described.
Acknowledgment. The authors acknowledge support of UNAM-PAPIT
IN106520, INRIA-Mexico Associate
Team, CNRS-Mexico UMI.
1. Alpern, B. and Schneider, F.B. Defining liveness.
Information Processing Letters 21, 4 (1985), 181–18.
2. Attiya, H., Bar-Noy, A., and Dolev, D. Sharing memory
robustly in message-passing systems. JACM 42, 1
3. Attiya, H., Ellen, F. and Morrison, A., Limitations of
highly-available eventually-consistent data stores.
IEEE Trans. Parallel Distributed Systems 28, 1 (2017),
4. Attiya, H. and Welch, J. Distributed Computing:
Fundamentals, Simulations and Advanced Topics, (2nd
Edition), Wiley, 2004.
5. Ben-Or, M. Another advantage of free choice:
completely asynchronous agreement protocols.
In Proc. 2nd ACM Symp. on Principles of Distributed
Computing, (1983), 27–30.
6. Brinch, H.P. (Ed.). The Origin of Concurrent Programming.
7. Cachin, C. State machine replication with Byzantine
faults. Replication. Springer LNCS 5959, (2011), 169–184.
8. Chandra, T. D., Hadzilacos, V., and Toueg, S. The
weakest failure detector for solving consensus. JACM
43, 4 (1996), 685–722.
9. Calciu, I., Sen, S., Balakrishnan, M., and Aguilera, M.
How to implement any concurrent data structure for
modern servers. ACM Operating Systems Rev. 51, 1
10. Castañeda, A., Rajsbaum, S., and Raynal, M. Unifying
concurrent objects and distributed tasks: Interval-linearizability. JACM 65, 6 (2018), Article 45.
11. Dijkstra, E. W. Solution of a problem in concurrent
programming control. Comm. ACM 8, 8 (Sept. 1965), 569.
12. Dijkstra, E. W. Cooperating sequential processes.
Programming Languages. Academic Press, 1968, 43–112.
13. Dijkstra, E. W. Hierarchical ordering of sequential
processes. Acta Informatica 1, 1 (1971), 115–138.
14. Dolev, D., Dwork, C., and Stockmeyer, L. On the
minimal synchronism needed for distributed
consensus. JACM 34, 1 (1987), 77–97.
15. Fatourou, P. and Kallimanis, N.D. Highly-efficient wait-free synchronization. Theory of Computing Systems 55
16. Fischer, M.J., Lynch, N.A., and Paterson, M.S.
Impossibility of distributed consensus with one faulty
process. JACM 32, 2 (1985), 374–382.
17. Gilbert, S. and Lynch, N. Brewer’s conjecture and the
feasibility of consistent, available, partition-tolerant
web services. SIGACT News 33, 2 (2002), 51–59.
18. Hadzilacos, V. and Toueg, S. A modular approach to
fault-tolerant broadcasts and related problems. TR
94-1425. Cornell Univ. (1994)
19. Herlihy, M.P. Wait-free synchronization. ACM Trans. on
Prog. Languages and Systems 13, 1 (1991), 124–149.
20. Herlihy, M.P. and Moss, J.E.B. Transactional memory:
Architectural support for lock-free data structures.
In Proc. 20th ACM Int’l Symp. Computer Architecture.
ACM Press, 1993, 289–300.
21. Herlihy, M. and Shavit, N. The Art of Multiprocessor
Programming. Morgan Kaufmann, ISBN 978-0-12-
22. Herlihy, M.P. and Wing, J.M. Linearizability: A
correctness condition for concurrent objects. ACM
Trans. Programming Languages and Systems 12, 2
23. Lamport, L. A new solution of Dijkstra’s concurrent
programming problem. Commun. ACM 17, 8 (1974),
24. Lamport, L. Concurrent reading and writing. Commun.
ACM 20, 11 (Nov. 1977), 806–811.
25. Lamport, L. Time, clocks, and the ordering of events
in a distributed system. Commun. ACM 21, 7 (Sept.
26. Lamport, L. On interprocess communication, Part I: Basic
formalism. Distributed Computing 1, 2 (1986), 77–85.
27. Lamport, L. A fast mutual exclusion algorithm. ACM
Trans. Computer Systems 5, 1 (1987), 1–11.
28. Lamport, L. The part-time parliament. ACM Trans.
Computer Systems 16, 2 (1998), 133–169.
29. Mostéfaoui, Rajsbaum, S. and Raynal, M. Conditions on
input vectors for concensus solvability in asynchronous
distributed systems. JACM 50, 6 (2003, 922–954.
30. Nakamoto, S. Bitcoin: A peer-to-peer electronic cash
system. Unpublished manuscript (2008).
31. Pease, M., Shostak, R. and Lamport, L. Reaching
agreement in the presence of faults. JACM 27 (1980),
32. Peterson, G.L. Myths about the mutual exclusion
problem. Information Processing Letters 12, 3 (1981),
33. Peterson, G.L. Concurrent reading while writing.
ACM Trans. on Prog. Languages and Systems (1983),
34. Rabin, M. Randomized Byzantine generals. Proc. 24th
IEEE Symp. Foundations of Computer Science. IEEE
Computer Society Press, 1983, 116–124.
35. Raynal, M. Concurrent Programming: Algorithms,
Principles and Foundations. Springer, 2013, ISBN 978-
36. Raynal, M. Distributed Algorithms for Message-Passing
Systems. Springer, 2013, ISBN 978-3-642-38122-5.
37. Raynal, M. Fault- Tolerant Message-Passing Distributed
Systems: An Algorithmic Approach. Springer, 2018,
38. Stearns, R.C., Lewis, P.M. and Rosenkrantz, D.J.
Concurrency control for database systems. In Proc.
16th Conf. Found. Comp. Sci., (1976), 19–32.
39. Schneider, F.B. Implementing fault-tolerant services
using the state machine approach. ACM Computing
Surveys 22, 4 (1990), 299–319.
40. Shavit, N. and Touitou, D. Software transactional
memory. Distributed Computing 10, 2 (1997), 99–116.
Sergio Rajsbaum ( email@example.com) is a professor
at the Instituto de Matematicas at the Universidad
Nacional Autónoma de Mexico inn Mexico City, México.
Michel Raynal ( firstname.lastname@example.org) is a professor at IRISA,
University of Rennes, France, and Polytechnic University in
© 2020 ACM 0001-0782/20/1