Linearizability in the Presence of Drifting Clocks and Under Different Delay Assumptions

Abstract. The cost of using message-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 perform-ing read and write operations in distributed implementations of virtual shared memory consisting of such objects. A collection of necessary con-ditions on these response times are presented for a large family of as-sumptions 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; inter-estingly, 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.