Consensus-Free Ledgers When Operations of Distinct Processes are Commutative

Davide Frey (1) , Lucie Guillou (2) , Michel Raynal (1) , François Taïani (1)

1 WIDE - the World Is Distributed Exploring the tension between scale and coordination
2 ENS Rennes - École normale supérieure - Rennes

Considering asynchronous message-passing systems in which any number of processes may crash, this article addresses the construction of ledger objects where (i) the append operations issued from distinct processes commute, while (ii) the append operations issued from the same process do not. In a very interesting way, it appears that the implementation of such ledgers does not need consensus, which makes them both attractive and efficient. Their underlying formalization rests on Mazurkiewicz's traces.

Mots clés: Asynchronous system; Blockchain; Commutative operations; Consensusfreedom; FIFO-based synchronization; Immutable memory; Mazurkiewicz's traces; Message-passing; Process crash failures; Reliable broadcast

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Davide Frey, Lucie Guillou, Michel Raynal, François Taïani. Consensus-Free Ledgers When Operations of Distinct Processes are Commutative. PaCT 2021 - 16th International Conference on Parallel Computing Technologies, Sep 2021, Kaliningrad, Russia. pp.359-370, ⟨10.1007/978-3-030-86359-3_27⟩. ⟨hal-03346756⟩