3 ms·
After reading the article and skimming some posts on their subreddit, I think the idea generally concerns the capabilities of consumer electronics to 'replicate
by law 15y ago
After reading the article and skimming some posts on their subreddit, I think the idea generally concerns the capabilities of consumer electronics to 'replicate' the Internet in a completely decentralized fashion. By doing so, there's no central authority managing your packets, and if you want to visit a particular node (i.e., to visit a web site), the problem becomes analogous to the stochastic shortest path problem, which is NP-complete. So, wouldn't this system require P = NP for it to have any viability at all when factoring in the effects of latency and downtime?
- joelthelion 15y agoMost NP-complete problems can be approximated quickly enough for practical purposes. Decentralized routing is a hard problem, but there has been a lot of research with pretty convincing results. I'm not sure if it scales to the size of the internet, though.
- law 15y agoThat's the point, though: I don't know if you can find an 'approximate' solution to decentralized routing, since you need precision. Do you have any peer-reviewed articles evidencing these convincing results? I'd be extremely interested in learning some more about this.
- pyre 15y agoWho is the current centralized authority that figures out the shortest routes today?
- law 15y agoDifference in definitions: I read "approximate solution" as an "approximate route," as in the node choices are approximated (potentially leading to a wrong final node, or losing packets at a dead end). Instead, finding approximately the shortest route that doesn't lose packets and gets you to the correct node would presumably work.
- wmf 15y agoThere has been some work in this area: http://www.cs.uiuc.edu/~caesar/papers/rofl.pdf http://www.cs.uiuc.edu/~caesar/papers/rofl.pdf http://www.dca.fee.unicamp.br/~pasquini/artigos/sbrc_2009.pdf http://www.dca.fee.unicamp.br/~pasquini/artigos/sbrc_2009.pd... http://www.cs.uiuc.edu/homes/pbg/papers/Scalable_Routing_on_Flat_Names.pdf http://www.cs.uiuc.edu/homes/pbg/papers/Scalable_Routing_on_... None of these find shortest paths; they aim to find paths that are within a constant factor of shortest.
- amalcon 15y agoYou really just need to find some reasonable route. Your current routes are very unlikely to be the shortest / cheapest / metric of choice; they are mostly decided politically.