The search functionality is under construction.

The search functionality is under construction.

We call a network an *anonymous network*, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions *A* and *B* (denoted by *A**B*) as the relation that some distributed algorithm can compute *B* on any network satisfying *A*. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions *k*-*LEADER* and *k*-*COLOR*. *k*-*LEADER* denotes the initial condition that gives special condition only to *k* vertices. *k*-*COLOR* denotes the initial condition that divides the vertices into *k* groups. Then we investigate the property of the relation among these initial conditions.

- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.12 pp.2029-2038

- Publication Date
- 2000/12/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section INVITED PAPER (Special Issue on the 1999 IEICE Excellent Paper Award)

- Category
- Theory and Models of Software

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Naoshi SAKAMOTO, "Structure of Initial Conditions for Distributed Algorithms" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 12, pp. 2029-2038, December 2000, doi: .

Abstract: We call a network an *anonymous network*, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions *A* and *B* (denoted by *A**B*) as the relation that some distributed algorithm can compute *B* on any network satisfying *A*. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions *k*-*LEADER* and *k*-*COLOR*. *k*-*LEADER* denotes the initial condition that gives special condition only to *k* vertices. *k*-*COLOR* denotes the initial condition that divides the vertices into *k* groups. Then we investigate the property of the relation among these initial conditions.

URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_12_2029/_p

Copy

@ARTICLE{e83-d_12_2029,

author={Naoshi SAKAMOTO, },

journal={IEICE TRANSACTIONS on Information},

title={Structure of Initial Conditions for Distributed Algorithms},

year={2000},

volume={E83-D},

number={12},

pages={2029-2038},

abstract={We call a network an *anonymous network*, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions *A* and *B* (denoted by *A**B*) as the relation that some distributed algorithm can compute *B* on any network satisfying *A*. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions *k*-*LEADER* and *k*-*COLOR*. *k*-*LEADER* denotes the initial condition that gives special condition only to *k* vertices. *k*-*COLOR* denotes the initial condition that divides the vertices into *k* groups. Then we investigate the property of the relation among these initial conditions.

keywords={},

doi={},

ISSN={},

month={December},}

Copy

TY - JOUR

TI - Structure of Initial Conditions for Distributed Algorithms

T2 - IEICE TRANSACTIONS on Information

SP - 2029

EP - 2038

AU - Naoshi SAKAMOTO

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E83-D

IS - 12

JA - IEICE TRANSACTIONS on Information

Y1 - December 2000

AB - We call a network an *anonymous network*, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions *A* and *B* (denoted by *A**B*) as the relation that some distributed algorithm can compute *B* on any network satisfying *A*. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions *k*-*LEADER* and *k*-*COLOR*. *k*-*LEADER* denotes the initial condition that gives special condition only to *k* vertices. *k*-*COLOR* denotes the initial condition that divides the vertices into *k* groups. Then we investigate the property of the relation among these initial conditions.

ER -