Is the Network Turing-Complete? EPFL Technical Report 187131
| Autor: | Perešíni, Peter, Kostic, Dejan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Zdroj: | IMDEA Networks Institute Digital Repository instname IMDEA Networks Institute |
| Popis: | Ensuring correct network behavior is hard. This is the case even for simple networks, and adding middleboxes only complicates this task. In this paper, we demonstrate a fundamental property of networks. Namely, we show a way of using a network to emulate the Rule 110 cellular automaton. We do so using just a set of network devices with simple features such as packet matching, header rewriting and round-robin loadbalancing. Therefore, we show that a network can emulate any Turing machine. This ultimately means that analyzing dynamic network behavior can be as hard as analyzing an arbitrary program. Analyzing a network containing middleboxes is already understood to be hard. Our result shows that using even only statically configured switches can make the problem intractable. pub |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|