Symmetry in port-labelled anonymous networks
| dc.contributor.author | Ren, Yongzhen | |
| dc.contributor.examiningcommittee | Gunderson, Karen (Mathematics) Kamali, Shahin (Computer Science) | en_US |
| dc.contributor.supervisor | Miller, Avery (Computer Science) | en_US |
| dc.date.accessioned | 2021-08-31T20:29:23Z | |
| dc.date.available | 2021-08-31T20:29:23Z | |
| dc.date.copyright | 2021-07-07 | |
| dc.date.issued | 2021-07 | en_US |
| dc.date.submitted | 2021-07-07T22:07:40Z | en_US |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.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. | en_US |
| dc.description.note | October 2021 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/35872 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | Algorithm, Degree tree, Distributed computing, Graph theory, Multiplicity, Symmetricity, View | en_US |
| dc.title | Symmetry in port-labelled anonymous networks | en_US |
| dc.type | master thesis | en_US |