We present an algorithm to simulate Read-Modify-Write registers in a message passing system with unreliable asynchronous processors and asynchronous communication. The algorithm works correctly in the presence of a strong adversary that can stop up to T processors, or stop the delivery of their messages where T = [N/2]-I and N is the number of processors in the system. This is the best resilience that can be achieved in the message passing systems. The high resilience of the algorithm is obtained by using randomized consensus algorithms and a robust communication primitive. The use of this primitive allows a processor to exchange local information with a majority of processors in a consistent way and therefore, make decisions safely. The simulator makes it possible to translate algorithms for the shared memory model to that for the message passing model. With some minor modifications the algorithm can be used to robustly simulate shared queues, shared stacks, etc. K e y words : Atomicity, asynchronous systems, consensus, message passing model, mutual exclusion, randomized algorithms, resiliense, shared memory model, synchronization primitives, Read-Modify-Write registers. 1 I n t r o d u c t i o n In the shared memory model for intercommunication in multiprocessor systems, several synchronization primitives have been proposed to coordinate actions among the processors. The most common use of these primitives is to resolve conflicts when there are concurrent requests of access to a shared resource. These primitives are also used when the processors need to select some unique values, e.g., id's, time stamps, etc. On the other hand, the agreement problems in which all processors select the same value can also be solved using these synchronization primitives. In all cases the purpose of a primitive is to let a processor execute some specific operation without being interrupted. The type of operations we are referring to always involves access to a shared data object and the uninterrupted (atomic) access to it is absolutely necessary to guarantee the correct execution of the operation. The most basic synchronization primitives are the atomic read and atomic write instructions. These instructions guarantee that concurrent reads and writes to the object will be executed in a serial manner according to some definite order to maintain consistency of the shared data. A thorough study of these primitives can be found in , , , , , *This research was supported in part by the U. S Army Research Office under grant DAAL03-87-G-0004 and by the Information Science Research Institute, University of Nevada, Las Vegas.
Download Full PDF Version (Non-Commercial Use)