New Algorithms and Primitives for Multi-Processor Coordination

摘要

This thesis presents new approaches to several basic coordination problems thatarise in the context of distributed computation, such as bounded concurrent timestamping (abstracts the problem of temporally ordering concurrent events in an asynchronous shared memory system) and implementing a linearizable shared counter. In addition, the thesis identifies, isolates and solves several new basic problems such as time-lapse snapshot (abstracts the problem of enabling a processor to take an almost consistent picture of a region in shared memory that is being updated by concurrent processors), the traceable use abstraction (serves to convert an unbounded algorithm into a bounded one), and the problem of guaranteeing that work is performed despite the failure of some processors (captures one of the fundamental aspects of fault tolerance). (Copyright (c) 1992 by Orli Waats.)