search

ledgerloops / strategy-pit

Testing ground for LedgerLoop strategies
Apache License 2.0
0 stars 0 forks source link

Design loop tracing for Stingray #5

Closed michielbdejong closed 3 months ago

michielbdejong commented 4 months ago

As I'm designing Stingray, having implemented the flood probes and pin probes from #4, there comes a point in the algorithm where a node becomes aware of a proof of loop and starts a loop trace. This loop trace is linked to the probeId and goes out in both directions.

In all cases a loop trace is started when a pin probe comes back.

       North
        |
West - Alice  - East
        |        |
       South ___/

What if you received a probe from multiple directions? One easy approach is to send the Loop trace back to the sender of the Probe message that triggered it. And when forwarding a Loop trace, there will generally only be one from of the Probe...

I'll draw some diagrams with Flood-Pin-Trace in different colours to see if this works.

michielbdejong commented 4 months ago

Don't skip the PIN!

FLOOD may find a loop in a P shape, where the origin is not on the loop. Sending a PIN back, it will spread along both directions of the FLOOD, and ensure that when that loops back, it's a single-direction loop. Then the TRACE can go into the opposite direction to single out the right branch of the PIN tree.

michielbdejong commented 3 months ago

Reusing this design for Butterfly