Networks of hosts implementing DNS are NP-complete
Loading...
Date
2019-08-13
Authors
Kolybabi, Mak
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
NP-complete, Computer science, CSAT, DNS