LCS Publication Details
Publication Author: Attiya, Hagit
Additional Authors: Bar-Noy, Amotz., Dolev, Danny
LCS Document Number: MIT-LCS-TM-423
Publication Date: 2-1-1990
LCS Group: No Group Specified
Additional URL: No URL Given
Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures. These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed systems. Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems. The overhead introduced by these emulations is polynomial in the number of processors in the systems. Immediate new results are obtained by applying the emulators to known shared-memory algorithms. These include, among others, protocols to solve the following problems in the message-passing model in the presence of processor or link failures: multi-writer multi-reader registers, concurrent time stamp systems, -exclusion, atomic snapshots, randomized consensus, and implementation of a class of data structures.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.