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 |
id |
cracm:10.1145/273865.273884 |
---|---|
record_format |
openpolar |
spelling |
cracm:10.1145/273865.273884 2024-06-02T08:12:48+00:00 Implementing sequentially consistent shared objects using broadcast and point-to-point communication Fekete, Alan Kaashoek, M. Frans Lynch, Nancy 1998 http://dx.doi.org/10.1145/273865.273884 https://dl.acm.org/doi/pdf/10.1145/273865.273884 en eng Association for Computing Machinery (ACM) Journal of the ACM volume 45, issue 1, page 35-69 ISSN 0004-5411 1557-735X journal-article 1998 cracm https://doi.org/10.1145/273865.273884 2024-05-07T12:58:08Z 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. Article in Journal/Newspaper Orca ACM Publications (Association for Computing Machinery) Journal of the ACM 45 1 35 69 |
institution |
Open Polar |
collection |
ACM Publications (Association for Computing Machinery) |
op_collection_id |
cracm |
language |
English |
description |
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. |
format |
Article in Journal/Newspaper |
author |
Fekete, Alan Kaashoek, M. Frans Lynch, Nancy |
spellingShingle |
Fekete, Alan Kaashoek, M. Frans Lynch, Nancy Implementing sequentially consistent shared objects using broadcast and point-to-point communication |
author_facet |
Fekete, Alan Kaashoek, M. Frans Lynch, Nancy |
author_sort |
Fekete, Alan |
title |
Implementing sequentially consistent shared objects using broadcast and point-to-point communication |
title_short |
Implementing sequentially consistent shared objects using broadcast and point-to-point communication |
title_full |
Implementing sequentially consistent shared objects using broadcast and point-to-point communication |
title_fullStr |
Implementing sequentially consistent shared objects using broadcast and point-to-point communication |
title_full_unstemmed |
Implementing sequentially consistent shared objects using broadcast and point-to-point communication |
title_sort |
implementing sequentially consistent shared objects using broadcast and point-to-point communication |
publisher |
Association for Computing Machinery (ACM) |
publishDate |
1998 |
url |
http://dx.doi.org/10.1145/273865.273884 https://dl.acm.org/doi/pdf/10.1145/273865.273884 |
genre |
Orca |
genre_facet |
Orca |
op_source |
Journal of the ACM volume 45, issue 1, page 35-69 ISSN 0004-5411 1557-735X |
op_doi |
https://doi.org/10.1145/273865.273884 |
container_title |
Journal of the ACM |
container_volume |
45 |
container_issue |
1 |
container_start_page |
35 |
op_container_end_page |
69 |
_version_ |
1800759359591940096 |