| Autor: |
Bonin, Grégoire, Mostefaoui, Achour, Perrin, Matthieu |
| Přispěvatelé: |
Gestion de Données Distribuées (GDD), Laboratoire des Sciences du Numérique de Nantes (LS2N), 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)-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), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT) |
| Jazyk: |
angličtina |
| Rok vydání: |
2019 |
| Předmět: |
|
| Popis: |
In large scale distributed systems, replication is essential in order to provide availability and partition tolerance. Such systems are abstracted by the wait-free model, composed of asynchronous processes that communicate by sending and receiving messages, and in which any process may crash. Complexity in local memory has already been studied for several objects, including sets, databases and collaborative editors. However, the literature has focused on a subclass of algorithms, called the operational model, in which processes can only broadcast one message per update operation and the read operation incurs no communication. This paper tackles the following question: are the operational model and the wait-free model equivalent from the complexity point of view? We show that update consistency allows implementations in the wait-free model that require strictly less local memory than their counterparts in the operational model. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
