de-duplicate loops

[michielbdejong]

In #31 I'm not finding:

Loops found:
3 [ 'stocking fly' ]
4 []
6 [ 'confess decisive', 'milk reach' ]

All three loops are valid but this is a triangle so we can collaboratively deduplicate to only one loop, and then also make sure all participating nodes become aware of it.

[michielbdejong]

This propose stops at 4 even though 4 previously forwarded the milk reach rigid kite leg trace up the other leg to 6:

8: [3]->[4] propose milk reach rigid f2cd4d6db47568557a152a19eac5ce45dcc6bfeedfc5de4720415a3f60c47f95 1

The debug logs show that even though 4 did send:

6: [4]->[6] trace milk reach rigid

It apparently didn't record that as a forward:

  '[Node#receiveMessage] 4 receives message from 3',
  'Looking for a party in milk reach with rigid other than 3 in created: undefined',
  'Looking for a party in milk reach with rigid other than 3 in forwarded: {"3":"rigid","6":"collar"}',
  'other party not found for 3 propose milk reach rigid f2cd4d6db47568557a152a19eac5ce45dcc6bfeedfc5de4720415a3f60c47f95 1',

[michielbdejong]

The logs of sending milk reach rigid up the milk reach collar leg are:

  '[TraceEngine] handling trace message from 3: trace milk reach rigid',
  'checking if we have seenThisTraceBefore milk reach rigid in {"6":"collar"}',
  'tracesForwarded now looks like this: {"stocking":{"fly":{"3":"possible","6":"possible"}},"milk":{"reach":{"3":"rigid","6":"collar"}},"confess":{"decisive":{"3":"wanting","6":"wanting"}}}',
  '[Node#lookup-probe] 4 is looking up probe milk',
  '[TraceEngine] forwarding a counter-probe-wise trace message from 3: trace milk reach rigid',
  'Looking for other leg milk reach rigid in {"3":"rigid","6":"collar"}',
  '[TraceEngine] in the context of trace message from 3: trace milk reach rigid, we found these counter-probe-wise next hops: [], and otherLeg 6',
  '[TracesEngine] found otherLeg 6 for trace reach of probe milk',
  '[traceEngine.on-message] 4 sends trace message to 6: trace milk reach rigid',

[michielbdejong]

Hm, let me think...
At some point a node may see a trace loop back to itself and send out a loop announcement. It could send this announcement in both directions, but Badger sends it just forward trace-wise.
If it already knows of other loops for that trade-pair, then it will include those in the announcement.
This basically merges those loops to one loop with multiple traces.
Except when a fork is met during announcement forwarding.
If that happens, the announcement specs are split and the appropriate smaller announcement messages are sent forward.
When an announcement message loops back, at least partially intact, a propose can be triggered for its first spec.
If there are more specs on there that loop all the way round, a remove can be specified for those.

This really feels pretty collaborative, there are several ways in which a Byzantine node could use this system to destroy loops, so maybe this mechanism will not make it into production, but good deduplication makes debugging easier so I'm putting it into Badger and then we can experiment with it.

[michielbdejong]

I implemented parts of this now with https://github.com/ledgerloops/strategy-pit/commits/badger-sarafu/ - continuing tomorrow!

[michielbdejong]

loops are stored in the announce direction

[michielbdejong]

This line in the debug log of node 4 is weird, since 4 forwarded this trace from 3 to 6:

'Looking for a party in stocking fly with possible in forwarded: {"3":"possible","6":"possible"}',

[michielbdejong]

OK, the announcements work now, and all three nodes find all three loops correctly.
What worries me is that although the milk loop is announced by 6 as a duplicate of confess, the stocking loop is announced by 4 as unique due to timing.
So I can think of a few ways to fix that:

• include traces as well as confirmed loops as duplicates
• send extra announcement (maybe with an announcementId to track them) later

I'll try the first one first, and then see if i can implement duplicate removal somehow

[michielbdejong]

I had code that adds loops from announce but now that the announcement also contains mere traces as equivalents, I changed this to only store the first one if unknown.

[michielbdejong]

Only the announcement initiator can determine the equivalents, so it should be sending out a merge message once the announce has looped back, and then the group name can be the alphabetic concatenation of the group member loops.

[michielbdejong]

But first I need to fix the issue that ANNOUNCE COMPLETE doesn't trigger a propose -> #34

[michielbdejong]

I've now added deduplication in the end analysis in ./src/run.js - will leave it at that for now.