Networks of hosts implementing DNS are NP-complete
| dc.contributor.author | Kolybabi, Mak | |
| dc.contributor.examiningcommittee | Cameron, Helen (Computer Science) | en_US |
| dc.contributor.examiningcommittee | Graham, Peter (Computer Science) | en_US |
| dc.contributor.examiningcommittee | Jeffrey, Ian (Electrical & Computer Engineering) | en_US |
| dc.contributor.supervisor | Domaratzki, Michael (Computer Science) | en_US |
| dc.date.accessioned | 2019-09-12T20:23:49Z | |
| dc.date.available | 2019-09-12T20:23:49Z | |
| dc.date.issued | 2019-08-13 | en_US |
| dc.date.submitted | 2019-08-13T21:06:25Z | en |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.abstract | The Internet core protocols are the networking protocols that the Internet is built on, a subset of which are implemented on every device connected to the Internet. The specifications of these protocols can span dozens of documents, making accurately understanding and implementing them difficult. The Domain Name System is one of the Internet's core protocols, providing a distributed, hierarchical database primarily intended to map between the names and addresses of hosts. Modern DNS contains a plethora of complex and interacting features, defined across a number of documents, evolving over the course of over thirty years. I show that a network of specially-configured hosts implementing a subset of DNS operate as logic gates. I then describe how such gates can communicate to form Boolean circuits. Finally, I discuss CSAT and NP-completeness. | en_US |
| dc.description.note | October 2019 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/34243 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | NP-complete | en_US |
| dc.subject | Computer science | en_US |
| dc.subject | CSAT | en_US |
| dc.subject | DNS | en_US |
| dc.title | Networks of hosts implementing DNS are NP-complete | en_US |
| dc.type | master thesis | en_US |