Failure Tables
Failure tables have been either implemented or suggested various times, either as a way of limiting the load caused by polling clients, or as a way of making it more likely that frequently requested keys are found.
In 0.4/0.5, for a while, failure tables were implemented in the node: If a key was requested, and got a DNF, the node would remember this and for a limited time it would always return DNF immediately for any requests for that key (provided the HTL was no higher than that when it was first requested). The problem with this is that it could be self-seeding: Requests automatically set up failure tables, and more requests can propagate the failure table to more nodes. A key can become almost permanently unavailable, just because of failure table entries spawning more failure table entries (especially with probabilistic HTL). This can happen either accidentally or as a deliberate attack (e.g. requesting the key widely just before it is expected to be inserted) So we removed it. (Frost is actually quite gentle nowadays, which is another reason to remove it).
One way to solve that problem is to have a separate failure message for when a request was rejected because of failure tables, which would not cause failure table entries to be set up. Thus we can have failure tables, limit polling-derived load, and still avoid the above problems.
A proposal from a little later was Per-Node Failure Tables. The basic idea here is to remember which nodes we have routed a specific key to, and possibly how many times we have routed to them, and not route the same way twice. Thus, if the data is on the network, it should eventually be found. And if a node tries to censor a specific key, it will be routed around (this is a good thing). The only problem with this is that if the data isn't on the network, when it is eventually inserted it may not be found quickly.
A more recent proposal is Ultra-Lightweight Passive Requests. This is a combination of failure tables and a limited form of passive requests. The node remembers both which nodes the key has been routed to, and which nodes have asked it for the key. If the key is DNFed, then for a certain period it will fail incoming requests for that key (possibly with a non-DNF error message as above) - provided that it has already routed it to the node which is currently the best routing option for the key. But if it does get the key, it will offer it to all the nodes who have asked for it, and possibly all the nodes who it has asked for it too. Thus, we severely limit load from polling, and we provide a good chance of the key being found - quickly - when it is inserted, or, if enough nodes are requesting it, that it will be found even though it's in the wrong place on the network.
