| dc.description.abstract | The field of distributed computing has given rise to many algorithms to share data among nodes in a network. This work focuses on the store-collect and the atomic snapshot objects in an asynchronous, crash-prone message-passing dynamic system with nodes continuously entering and leaving the system. We assume that the maximum number of nodes that enter, leave or crash during some time interval is proportional to the size of the system. A store-collect object is a distributed object that allows nodes to store data in the system in a variable that can be read by all nodes, but only modified by the node that stored it. This is achieved through two basic operations: the store operation, which stores information into the network, and collect, which collects a copy of all the information stored by every node in the network at the beginning of the time interval in which the operation is active. The atomic snapshot object is quite similar. It provides two operations, scan and update, that behave in a very similar fashion to the collect and store operations given by the store-collect object; however the atomic snapshot object must satisfy the linearizability condition, which means that it is always possible to arrange all the operations performed into an ordered sequence even if there are operations that occur simultaneously. This work improves upon the store-collect and atomic snapshot implementations given in Attiya et al [SSS, 2020]. We developed a method for quantifying the churn of a network subject to certain assumptions. This new method allows us to prove the correctness of the store-collect algorithm under less restrictive conditions than those found in the original proof of Attiya et al. Additionally, we developed an improved implementation of the atomic snapshot object based on a store-collect object that requires fewer messages to complete a scan or an update operation. | en |
