Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks
Summary :
This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.620-626
- Publication Date
- 2000/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Naoshi SAKAMOTO, "Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 620-626, April 2000, doi: .
Abstract: This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_620/_p
Copy
@ARTICLE{e83-a_4_620,
author={Naoshi SAKAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks},
year={2000},
volume={E83-A},
number={4},
pages={620-626},
abstract={This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 620
EP - 626
AU - Naoshi SAKAMOTO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.
ER -
English
