Abstract—View is a labeled directed graph containing all information about the network that a party can learn by exchanging messages with its neighbors. View can be used to solve distributed problems on an anonymous network (i.e., a network that does not guarantee that every party has a unique identifier). This paper presents an algorithm that constructs views in a compressed form on an anonymous -party network of any topology in at most rounds with bit complexity, where the time complexity (i.e., the number of local computation steps per party) is . This is the first view-construction algorithm that runs in rounds with polynomial bits complexity. The paper also gives an algorithm that counts the number of nonisomorphic views in the network in time complexity if a view is given in the compressed form. These algorithms imply that some well-studied problems, including the leader election problem, can deterministically be solved in rounds with polynomial bit and time complexity on an anonymous -party network of any topology.
projects9.com
Phone : +91-9618855666
+91-8008855666
Email : projects[at]projects9.com