TY - JOUR

T1 - Computing on anonymous networks

T2 - Part I - Characterizing the solvable cases

AU - Yamashita, Masafumi

AU - Kameda, Tsunehiko

N1 - Funding Information:
This work was supported in part by the Natural Sciences and Engineering Council of Canada and a Scientific Research Grant-in-Aid from the Ministry of Education, Science, and Culture of Japan.

PY - 1996

Y1 - 1996

N2 - In anonymous networks, the processors do not have identity numbers. We investigate the following representative problems on anonymous networks: (a) the leader election problem, (b) the edge election problem, (c) the spanning tree construction problem, and (d) the topology recognition problem. On a given network, the above problems may or may not be solvable, depending on the amount of information about the attributes of the network made available to the processors. Some possibilities are: (1) no network attribute information at all is available, (2) an upper bound on the number of processors in the network is available, (3) the exact number of processors in the network is available, and (4) the topology of the network is available. In terms of a new graph property called symmetricity, in each of the four cases (1)-(4) above, we characterize the class of networks on which each of the four problems (a)-(d) is solvable. We then relate the symmetricity of a network to its 1- and 2-factors.

AB - In anonymous networks, the processors do not have identity numbers. We investigate the following representative problems on anonymous networks: (a) the leader election problem, (b) the edge election problem, (c) the spanning tree construction problem, and (d) the topology recognition problem. On a given network, the above problems may or may not be solvable, depending on the amount of information about the attributes of the network made available to the processors. Some possibilities are: (1) no network attribute information at all is available, (2) an upper bound on the number of processors in the network is available, (3) the exact number of processors in the network is available, and (4) the topology of the network is available. In terms of a new graph property called symmetricity, in each of the four cases (1)-(4) above, we characterize the class of networks on which each of the four problems (a)-(d) is solvable. We then relate the symmetricity of a network to its 1- and 2-factors.

UR - http://www.scopus.com/inward/record.url?scp=0029752472&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029752472&partnerID=8YFLogxK

U2 - 10.1109/71.481599

DO - 10.1109/71.481599

M3 - Article

AN - SCOPUS:0029752472

SN - 1045-9219

VL - 7

SP - 69

EP - 89

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 1

ER -