On the Implementation of Local Synchrony

Author:Wagner, Jr, Department of Computer ScienceUniversity of Virginia

Local synchrony is a distributed approach to providing logically synchronous capabilities in an asynchronous system. Local synchrony provides a logical timeline to memory access, and thus a total ordering to the steps of a distributed computation, without many of the inherent consequences of global synchronization. Local synchrony offers a framework for the implementation of various concurrency control mechanisms, including combining and isochrons (parallel operations). We show the implementability of local synchrony, and demonstrate its compatibility with existing protocols for fault-tolerance in general purpose multiprocessors. The results of our research are threefold. We show first that practical implementation of local synchrony is feasible in general, asynchronous, MIMD architectures. We show that such implementations are compatible with existing hardware fault tolerance systems and present a correct rollback algorithm for our general implementation. Finally, we present both analytic and empirical studies which illustrate the performance characteristics of such implementations. Our analytic modeling technique extends in novel ways probabilistic modelling methods often employed for interconnec- tion networks. Our work establishes the practicality and feasibility of local synchrony as a means of providing support for concurrency control.

All rights reserved (no additional license for public reuse)
Source Citation:

Wagner, Jr. "On the Implementation of Local Synchrony." University of Virginia Dept. of Computer Science Tech Report (1993).

University of Virginia, Department of Computer Science
Published Date: