Leader election problem on networks in which processor identity numbers are not distinct

Author

Yamashita, Masafumi ; Kameda, Tsunehiko

Author_Institution

Dept. of Comput. Sci. & Commun. Eng., Kyushu Univ., Fukuoka, Japan

Volume

10

Issue

9

fYear

1999

fDate

9/1/1999 12:00:00 AM

Firstpage

878

Lastpage

887

Abstract

In the networks considered in this paper, processors do not have distinct identity numbers. On such a network, we discuss the leader election problem and the problem of counting the number of processors having the same identity number. As the communication mode, we consider port-to-port, broadcast-to-port, port-to-mail box, and broadcast-to-mailbox. For each of the above communication modes, we present: an algorithm for counting the number of processors with the same identity number; an algorithm for solving the leader election problem; and a graph theoretical characterization of the solvable class for the leader election problem

Keywords

fault tolerant computing; graph theory; multiprocessor interconnection networks; parallel architectures; broadcast-to-mailbox; broadcast-to-port; communication mode; fault tolerance; graph theory; leader election problem; multiprocessor interconnection; port-to-mail box; port-to-port; processor identity numbers; Intelligent networks; Nominations and elections;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.798313

Filename

798313