Browse Prior Art Database

SIMPLE AND EFFICIENT DISTRIBUTED ALGORITHMS FOR ELECTION IN COMPLETE NETWORKS

IP.com Disclosure Number: IPCOM000128340D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Yehuda Atek: AUTHOR [+3]

Abstract

The message complexity of an election algorithm in a general network is [Equation ommitted] Recently, an O(n logn) election algorithm for a complete network was presented [8J. However, the algorithm is quite complicated in terms of understanding and programming. Here, we present simple and short election algorithms which are as efficient. The suggested algorithms are of practical importance for user' who are actually interested in programming the election algorithm on a complete network of processors.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SIMPLE AND EFFICIENT DISTRIBUTED ALGORITHMS FOR ELECTION IN COMPLETE NETWORKS

Yehuda Atek Eli Gafii Report No. CSD SIMPLE AND EFFICIENT DISTRIBUTED ALGORITHMS FOR ELECTION IN COMPLETE NETWORKS

YEHUDA AFEK ELI GAFNI Computer Science Department University of California, Los Angeles, CA 90024

Abstract

The message complexity of an election algorithm in a general network is

(Equation Omitted)

Recently, an O(n logn) election algorithm for a complete network was presented [8J. However, the algorithm is quite complicated in terms of understanding and programming. Here, we present simple and short election algorithms which are as efficient. The suggested algorithms are of practical importance for user' who are actually interested in programming the election algorithm on a complete network of processors.

1 Introduction

The election algorithm is an identical program residing in every node in the net-work. Initially, nodes differ only by their identifiers (ids). The nodes elect a leader by exchanging messages. When the message exchange terminates, one node. is distinguished from all others.

In

(Equation Omitted)

election algorithm for general networks was presented where m is the number of links and, n is the number of nodes in the network. It was later proven in

(Equation Omitted)

is a lower bound. A lower bound of 0(m) is obvious since any untraversed link could be the only link connecting two parts of the network, each holding a separate election algorithm.

In, (8J Korach et. al. showed that the 0(m) lower bound does not hold for the special case of a complete network, i.e., when every node has a link to every other node in the network. The authors then presented an election algorithm for complete networks. The algorithm follows that presented in (5J and, in terms of understanding and program-ming, is as complex.

UCLA Page 1 Dec 31, 1984

Page 2 of 10

SIMPLE AND EFFICIENT DISTRIBUTED ALGORITHMS FOR ELECTION IN COMPLETE NETWORKS

*This research was supported by the Defense Advanced Research Projects Agency of the Department of Defense under Contract MDA 903-82-C-0084. The first author is an IBM Graduate Fellow.

n complete networks, an election algorithm may terminate if all the the neighbors of one node have been visited. This is not the case in the general network. Taking advantage of the simplicity of termination detection, we apply principles suggested in (4,5J for general networks to derive two simple and elegant algorithms (A and B) for elec-tion in complete networks. The two algorithms present a tradeoff between time and mes-sage complexities. Algorithm A has as O(n) time complexity and

(Equation Omitted)

message complexity. Algorithm B has a 2*n*logn message complexity but an 0(n-logn) time com-plexity. Analyzing the communication and time complexities of the two algorithms, we derive a third algorithm, algorithm C, whose time complexity is 0(n) and communication complexi...