[MLS] Cost of the partial-tree approach

[Richard Barnes <[e-mail]>]

Hey all,

There was some debate at the interim about the performance implications of
the "partial-tree" approach to adds and removes [0] (derived from the
"remove-without-double-join" approach described on the mailing list [1]).
In particular, EKR expressed concern that this approach would cause message
size to degrade from log to linear.  To test this out, on the plane home I
wrote a simulator that performs random group operations and compares two
approaches:

1. The "full-tree" approach, which has optimal efficiency but also has
double-joins
2. The "partial-tree" approach, which has no double-joins but sub-optimal
efficiency

I've made a little visualizer here:

https://ipv.sx/treekem/blanking/

The tl;dr is that the partial-tree approach is only very bad if you have a
very sparse tree, in particular, if you follow the "Init w/o 2J" approach
of [0].  In all other cases, as long as updates happen sufficiently
frequently, the two approaches are within a small constant factor of one
another.  The intuition here is that adds / removes degrade the tree (since
they add blank nodes) while updates heal the tree (since they fill in blank
nodes).

If you have the simulator start out with a sparse tree (untick "Start
full"), you'll see that initially, the "partial-tree" approach is very bad,
pretty much linear, but it gets better as nodes update, and eventually
merges with the "full-tree" line.  If you start with a full tree, the lines
don't diverge.

Obviously, this isn't dispositive in one direction or another.  But ISTM
that this experiment indicates that the cost of the "partial-tree" approach
might not be too bad, given that it clears up a significant ambiguity /
saves the cost of double-join bookkeeping.

--Richard

[0]
https://github.com/mlswg/wg-materials/blob/master/interim-2018-09/no_more_double_joins.pdf
[1] https://mailarchive.ietf.org/arch/msg/mls/Zzw2tqZC1FCbVZA9LKERsMIQXik