Reducing the search space for probes

[michielbdejong]

If we make the product decision #36 to say we want to find all comms loops and not just all credit loops then this does mean on the technical side we can't really use max-flow. The idea of how MTCS uses max-flow is tightly connected to the credit graph being a directed graph.

So we could either look at a form of pre-processing (preceding the probe) that would work on an undirected graph, or using something like nack messages to stop unfruitful probe flooding trees early.

And in any case, if we use pre-processing then it needs to be adaptive to network links being added/removed.

[michielbdejong]

In a directed graph, nodes could tell each other how far away they are from the edge of the network.
Actually, maybe there is no reason this wouldn't also work in a bidirectional graph.
And maybe the measure would then not be how many steps you can go without hitting a leaf, but how many steps you can go without repeating links.
Would this be a privacy concern?

[michielbdejong]

Of course, when two nodes meet, they might both think they are e.g. 17 hops from the edge, and in a directed graph this would work, you can add that up, the total would be 17+1+17.
But in an undirected graph it might well be that there is a link in common.
So maybe I'll work on directed graphs first!

[michielbdejong]

What would also be really helpful for reducing the search space is if probes were prohibited from following the full path of an already traced loop

[michielbdejong]

Probes could easily record which announced loops they are forked on, or make sure they don't follow both directions of a loop

[michielbdejong]

Probes also don't have to enter known dead ends