For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
distributed algorithms, anonymous networks, leader election,
Full Text: PDF>>
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.