Linearizability in the presence of drifting clocks and under different delay assumptions

Abstract

The cost of usingmessag e-passing to implement linearizable read/write objects for shared memory multiprocessors with drifting clocks is studied. We take as cost measures the response times for performingread and write operations in distributed implementations of virtual shared memory consistingof such objects. A collection of necessary conditions on these response times are presented for a large family of assumptions on the network delays. The assumptions include the common one of lower and upper bounds on delays, and bounds on the difference between delays in opposite directions. In addition, we consider broadcast networks, where each message sent from one node arrives at all other nodes at approximately the same time. The necessary conditions are stated in the form of “gaps” on the values that the response times may attain in any arbitrary execution of the system

the ends of the gap intervals depend solely on the delays in a particular execution, and on certain fixed parameters of the system that express each specific delay assumptions. The proofs of these necessary conditions are comprehensive and modular

they consist of two major components. The first component is independent of any particular type of delay assumptions

it constructs a “counter-example” execution, which respects the delay assumptions only if it is not linearizable. The second component must be tailored for each specific delay assumption

it derives necessary conditions for any linearizable implementation by requiring that the “counter-example” execution does not respect the specific delay assumptions. Our results highlight inherent limitations on the best possible cost for each specific execution of a linearizable implementation. Moreover, our results imply lower bounds on the worst possible such costs as well

interestingly, for the last two assumptions on mesage delays, these worst-case lower bounds are products of the drifting factor of the clocks and the delay uncertainty inherent for the specific assumption. © Springer-Verlag Berlin Heidelberg 1999.