Symmetry in port-labelled anonymous networks
Loading...
Date
2021-07
Authors
Ren, Yongzhen
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Our work investigates symmetry in a port-labelled anonymous network, a relatively weak but yet useful model of computation in distributed computing. In such a network, nodes have no identifiers, and for each node v, its incident links are labelled bijectively with the integers {1, 2, …, deg(v)} called ‘ports’. Each node has access to its ‘view’, a mathematical object completely representing the information that the node can learn from communicating with its neighbours. The question that arises is to understand how many nodes have their identities uniquely determined by such a view and what parameters for the number of nodes sharing a similar view are possible. This thesis provides a detailed survey in this area and addresses a number of new questions (detailed in Chapter 3). Applications and related problems of port-labelled anonymous networks are explained in Chapter 4. The new results are presented in Chapters 5, 6, and 7. Some open problems are given in Chapter 8 and Appendix B.
Description
Keywords
Algorithm, Degree tree, Distributed computing, Graph theory, Multiplicity, Symmetricity, View