Performance evaluation of an efficient multiple copy update algorithm

摘要

The authors study the response-time behavior of a symmetric distributed update-synchronization algorithm where nodes need to obtain permission from only O( square root N) (N being the number of database copies) other nodes before performing an update (as opposed to N/2+1 nodes in the well-known Thomas majority consensus algorithm). The algorithm used is an adaptation of M. Maekawa's O( square root N) distributed mutual exclusion algorithm (1985) to multiple-copy update-synchronization. This increase in the efficiency of the update-synchronization algorithm enhances performance in two ways. First, the reduction in transaction service time reduces the response time. Second, the decrease in response time reduces the number of waiting transactions in the system. This reduces the probability of conflict between transactions. To capture the interaction between the probability of conflict and the transaction response time, the authors define a new measure called the conflict response-time product. They show that optimizing this measure yields a different and more appropriate choice of system parameters than simply minimizing the mean transaction response time.