00000cab a22000003a 4500 UP-99796217608727526 Buklod 20231007234724.0 m |o d | ta 090226s xx d | ||r ||||| || (iLib)UPD-00077096439 DENGII eng Fekete, Alan Implementing sequentially consistent shared objects using broadcast and point-to-point communication. pp. 35-69 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. Computer systems organization. Computer communication networks. Distributed systems. Network operating systems. Software. Operating systems. Theory of computation. Logics and meanings of programs. Algorithms. Verification. Journal of the ACM 45, 1 (1998). FO UPD DENG-II Article