Speculative Prefetching of Optional Locks in Distributed Systems

T. Schöbel-Theuer (Germnay)


Resource Allocation, Distributed Locking, Distributed Al gorithms, Distributed Databases, Operating Systems


We present a family of methods for speeding up distributed locks by exploiting the uneven distribution of both tempo ral and spatial locality of access behaviour of many appli cations. In the worst case, some of our methods will not produce higher network latencies than equivalent conven tional distributed locking methods. In best case, the total number of messages can be constantly bounded, approxi mating the impression that no network latencies exist at all. Measurements and simulations based on variants of TPC database benchmarks show that hit rates enabled by speculative prefetching of optional locks appear to be sim ilar to hit rates of conventional data caches, typically in the range from 90% to 99%. Thus overall speedup factors of 10 or more for the average latencies of distributed locks are possible. Compared to purely temporal prefetching, adding exploitation of spatial locality may significantly improve performance, typically by factors of 2 or more. We discuss some implications for the construction of distributed systems. For the class of programs well-suited for distributed systems, network latencies will nearly van ish, blurring performance differences between local and distributed systems. For program classes exposing poor lo cality, there is likely no help independent from distributed computing paradigms. We explain how the communica tion paradigm can be efficiently implemented on top of dis tributed shared memory (DSM) using region locks. Thus we believe that the DSM paradigm will become more at tractive than explicit communication (e.g. RPC, CORBA) for the construction of distributed applications.

Important Links:

Go Back