Election protocols in distributed computing systems and distributed databases and their performance evaluation

摘要

In a distributed computing system, a change in the state of the system (site failure, network partition, merge after partition, etc.) usually requires that the new state be propagated to all active nodes so that they can correctly perform cooperative tasks. Since more than one node may detect a status change, conflicts in state determination and propagation are possible. In order to ensure that all nodes of a communicating group are at the same state, all nodes of the group must agree upon the election of a single coordinator.;The election protocols that were developed in the past were often dependent upon the network topology. In particular, a considerable amount of work had been done for systems in which nodes were arranged in a ring. Several protocols had been proposed for general networks, but they were largely developed under the assumption that there was no communication failures during the election process.;In this dissertation, an ambitious attempt to design election protocols for both ring and general configuration network was made. A linear election protocol for both synchronous and asynchronous ring networks (LEPR), and an election protocol for general configuration network (EPGC), were developed.;These protocols were analyzed for performance using both analytical techniques and simulation modeling. The performance evaluation showed that the LEPR protocol required $O(n)$ messages and $O(n)$ time in the worst case, a potentially significant improvement for large rings. It also showed that the EPGC protocol performed correctly and efficiently. The EPGC protocol was tested on different well known configurations. The study showed a trade off between the election time and the number of exchanged messages. A technique to minimize the number of messages was then introduced. Both positive and negative effects of this technique were observed.