Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model

Autor: Bonin, Grégoire, Mostéfaoui, Achour, Perrin, Matthieu
Přispěvatelé: Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN), Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Gestion de Données Distribuées (GDD), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: International Symposium on Distributed Computing (DISC) 2019
International Symposium on Distributed Computing (DISC) 2019, Oct 2019, Budapest, Hungary
Popis: International audience; In classical asynchronous distributed systems composed of a fixed number n of processes where some proportion may fail by crashing, many objects do not have a wait-free linearizable implementation (e.g. stacks, queues, etc.). It has been proved that consensus is universal in such systems, which means that this system augmented with consensus objects allows to implement any object that has a sequential specification. In this paper, we consider a more general system model called infinite arrival model where infinitely many processes may arrive and leave or crash during a run. We prove that consensus is still universal in this more general model. For that, we propose a universal construction based on a weak log that can be implementated using consensus objects.
Databáze: OpenAIRE
Externí odkaz: