Sharing Memory Robustly in Message-Passing Systems

摘要

Emulators that translate algorithms from the shared-memory model to two differentmessage-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, l-exclusion, atomic snapshots, randomized consensus, and implementation of a class of data structures. Keywords: Message passing; Shared memory; Dynamic networks; Fault tolerance; Wait-free algorithms; Emulations; Atomic registers. (kr)