Performance evaluation of the time-stamp ordering algorithm in a distributed database

摘要

Time-stamp ordering is one of the consistency preserving algorithms that is used in distributed databases. F. Baccelli (1987) has introduced a queueing model that incorporates the fork-join and resequencing synchronization constraints to analyze the algorithm's performance. The power of interpolation approximation technique is illustrated by obtaining extremely good approximations for this rather complex model. The heavy traffic approximations are obtained by showing that this model has the same diffusion limit as a system of parallel fork-join queues. The light traffic limits are obtained by applying the light traffic theory developed by M.I. Reiman and B. Simon (1989). The heavy traffic limits are computed for general arrival and service distributions, but the light traffic limits are restricted to Markovian systems.