Implementing sequentially consistent shared objects using broadcast and point-to-point communication
This paper presents and proves correct a distributed algorithm that implements a sequentially consistent collection of shared read/update objects. This algorithm is a generalization of one used in the Orca shared object system. The algorithm caches objects in the local memory of processors according...
| Published in: | Journal of the ACM |
|---|---|
| Main Authors: | , , |
| Format: | Article in Journal/Newspaper |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
1998
|
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1145/273865.273884 https://dl.acm.org/doi/pdf/10.1145/273865.273884 |
| Summary: | This paper presents and proves correct a distributed algorithm that implements a sequentially consistent collection of shared read/update objects. This algorithm is a generalization of one used in the Orca shared object system. The algorithm caches objects in the local memory of processors according to application needs; each read operation accesses a single copy of the object, while each update accesses all copies. The algorithm uses broadcast communication when it sends messages to replicated copies of an object, and it uses point-to-point communication when a message is sent to a single copy, and when a reply is returned. Copies of all objects are kept consistent using a strategy based on sequence numbers for broadcasts. The algorithm is presented in two layers. The lower layer uses the given broadcast and point-to-point communication services, plus sequence numbers, to provide a new communication service called a context multicast channel . The higher layer uses a context multicast channel to manage the object replication in a consistent fashion. Both layers and their combination are described and verified formally, using the I/O automation model for asynchronous concurrent systems. |
|---|