Implementing Sequentially Consistent Shared Objects using Broadcast and Point-To-Point Communication

• Main Authors: Alan Fekete, M. Frans Kaashoek, Nancy Lynch
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 1998
• Subjects: Orca
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.9865; http://theory.lcs.mit.edu/tds/papers/Fekete/orca-journal.ps

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