PERFORMANCE EVALUATION OF AN EFFICIENT MULTIPLE COPY UPDATE ALGORITHM

A well-known algorithm for updating multiple copies is the Thomas majo rity consensus algorithm. This algorithm, before performing an update, needs to obtain permission from a majority of the nodes in the system . In this short note, we study the response-time behavior of a symmetr ic (each node seeks permission from the same number of other nodes and each node receives requests for update permission from the same numbe r of other nodes) distributed update-synchronization algorithm where n odes need to obtain permission from only O(square-root N)(N being the number of database copies) other nodes before performing an update. Th e algorithm we use is an adaptation of Maekawa's O(square-root N) dist ributed mutual exclusion algorithm to multiple-copy update-synchroniza tion. This increase in the efficiency of the update-synchronization al gorithm enhances performance in two ways. First, the reduction in tran saction service time reduces the response time. Second, for a given ar rival rate of transactions, the decrease in response time reduces the number of waiting transactions in the system. This reduces the probabi lity of conflict between transactions. To capture the interaction betw een the probability of conflict and the transaction response time, we define a new measure called the conflict response-time product. Based on the solution of a queueing model we show that optimizing this measu re yields a different and more appropriate choice of system parameters than simply minimizing the mean transaction response time.