Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

FAST AND MESSAGE-OPTIMAL SYNCHRONOUS ELECTION ALGORITHM FOR COMPLETE NETWORKS

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

Publishing Venue

Software Patent Institute

Related People

Eli Gafni: AUTHOR [+5]

Abstract

In the election problem, a single processor, the leader, has to be distinguished from a set of processors which differ only by their identifiers (ids). Initially, no proces-sor is aware of the id of any other processor. The election algorithm is an identical program residing at each processor in the network. An arbitrary subset of processors spontaneously wake up at arbitrary times and start the algorithm by sending messages over the network. When the message exchange terminates, the leader is distinguished from all other processors. This paper addresses the problem of electing a leader in a synchronous complete network. In such a network, each pair of processors is connected by a bidirectional communication link, and all processors are connected to a global clock. We assume that all the links incident to a processor on which no message was sent or received are indistinguishable. For arbitrary asynchronous networks, [Equation ommitted] bound on the message complexity was proved [3, 4, 5, 7J, where n and m are the total number of processors and links in the network. 0(m) is a lower bound since no algorithm may terminate before sending at least one message over each link; otherwise, an untraversed link could be the only link connecting two parts of the network, each holding a separate election. Yet, Korach et al. (6J noted that the [Equation ommitted] lower bound does not hold in complete networks, where an election algorithm may terminate after one processor has communicated with all its neighbors. Subsequently they proved a lower bound of eeee messages for the asynchronous complete network and presented an algorithm that requires 5wlogn+O(n) messages and [Equation ommitted] time. For synchronous complete networks, [Equation ommitted] is also a lower bound on the mes-sage complexity, as is recently shown in [1J, where it is proved that [Equation ommitted] rounds is a *This research was supported by the Defense Advanced Research Projects Agency of the Department of Defense under Contract MDA 903-82-C-0064. The second author is an IBM Graduate Fellow.

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

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

FAST AND MESSAGE-OPTIMAL SYNCHRONOUS ELECTION ALGORITHM FOR COMPLETE NETWORKS

Eli Gafni Yehuda Afek Leonard Kleinrock October 1984 CSD-840041

FAST AND MESSAGE-OPTIMAL SYNCHRONOUS ELECTION ALGORITHM FOR COMPLETE NETWORKS

Eli Gafni Yehuda Afek Leonard Kleinrock

Computer Science Department University of California, Los Angeles, CA

1 Introduction

In the election problem, a single processor, the leader, has to be distinguished from a set of processors which differ only by their identifiers (ids). Initially, no proces-sor is aware of the id of any other processor. The election algorithm is an identical program residing at each processor in the network. An arbitrary subset of processors spontaneously wake up at arbitrary times and start the algorithm by sending messages over the network. When the message exchange terminates, the leader is distinguished from all other processors.

This paper addresses the problem of electing a leader in a synchronous complete network. In such a network, each pair of processors is connected by a bidirectional communication link, and all processors are connected to a global clock. We assume that all the links incident to a processor on which no message was sent or received are indistinguishable.

For arbitrary asynchronous networks,

(Equation Omitted)

bound on the message complexity was proved [3, 4, 5, 7J, where n and m are the total number of processors and links in the network. 0(m) is a lower bound since no algorithm may terminate before sending at least one message over each link; otherwise, an untraversed link could be the only link connecting two parts of the network, each holding a separate election. Yet, Korach et al. (6J noted that the

(Equation Omitted)

lower bound does not hold in complete networks, where an election algorithm may terminate after one processor has communicated with all its neighbors. Subsequently they proved a lower bound of eeee messages for the asynchronous complete network and presented an algorithm that requires 5wlogn+O(n) messages and

(Equation Omitted)

time.

For synchronous complete networks,

UCLA Page 1 Dec 31, 1984

Page 2 of 6

FAST AND MESSAGE-OPTIMAL SYNCHRONOUS ELECTION ALGORITHM FOR COMPLETE NETWORKS

(Equation Omitted)

is also a lower bound on the mes-sage complexity, as is recently shown in [1J, where it is proved that

(Equation Omitted)

rounds is a

*This research was supported by the Defense Advanced Research Projects Agency of the Department of Defense under Contract MDA 903-82-C-0064. The second author is an IBM Graduate Fellow. lower bound on the time complexity of any message optimal synchronous algorithm.

In this paper we employ the observation of Korack et al. (6j and the fact that in a complete network every processor may be the root of a star spanning tree to con-struct a synchronous election algorithm for complete networks, which attains the above message and time lower bounds. The message compl...