| 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. |
