#pragma section-numbers 2
<<Include(A:dev)>>

= 2.9 Sprint Obsolete Markers Notes =
Notes from the 2.9 development sprint pertaining to obsolete markers.

<<TableOfContents>>

== Cycles ==

{{{#!dot
digraph {
   rankdir = BT
   graph [nodesep=1.0]
   node [shape=record]
   revA [label="{A}", style="dashed"];
   revA1 [label="{A'}"];
   revA2 [label="{A''}"];
   revA -> revA2 [dir=back, style="dashed"]
   revA -> revA1 [dir=back, style="dashed"]
}
}}}

`A''` and `A'` both mark `A` obsolete, so you have a divergence. If Alice and Bob
handle that case separately, Alice may pick `A''` (by adding an obsolete marker
for `A'' -> A'`) and Bob may pick `A'` (by adding a marker for `A' -> A''`), thus
introducing a direct cycle between `A''` and `A'`.


{{{#!dot
digraph {
   rankdir = BT
   graph [nodesep=1.0]
   node [shape=record]
   revA [label="{A}", style="dashed"];
   revA1 [label="{A'}", nodesep=1.5];
   revA2 [label="{A''}", nodesep=2.0];
   revA -> revA2 [dir=back, style="dashed"];
   revA -> revA1 [dir=back, style="dashed"];
   revA1 -> revA2 [dir=back, style="dashed"];
   revA2 -> revA1 [dir=back, style="dashed"];
   {rank = same; revA1; revA2;}
}
}}}

== Exchange ==

Possible solutions for exchange, given we know the set of markers that should
be on the destination:

|| Solution    || sufficient || partial ||
|| hash tree   ||            ||         ||
|| boxed       || almost     ||         ||
|| rsync       ||            ||         ||
|| time bucket ||            ||  no?    ||

sufficient = does the solution transmit everything MUST send - that is, the
meta-history on both sides might mismatch, but the changeset history is correct
on both sides

partial = can the solution transmit less than all the markers that have ever
existed intelligently

box is "almost" sufficient for two reasons:
  1. We can't push isolated kills

{{{#!dot
digraph {
   rankdir = BT
   graph [nodesep=1.0]
   node [shape=record]
   revA [label="{A}"];
   revB [label="{B}"];
   revC [label="{C}", style="dashed"];
   revX [label="{X}"];
   revA -> revB [dir=back]
   revB -> revC [dir=back]
   revC -> revX [dir=back, style="dashed"]
   {rank = same; revC; revX;}
}
}}}

  That is, if C is already on the server in draft phase, we can't push the kill
  marker for C with boxpush as it's currently defined.

  1. You can't handle a marker appearing after a push. That is

{{{#!dot
digraph {
   rankdir = BT
   graph [nodesep=1.0]
   node [shape=record]
   revA [label="{A}", style="dashed"];
   revA1 [label="{A'}", style="dashed"];
   revA2 [label="{A''}"];
   revA -> revA1 [dir=back, style="dashed"]
   revA1 -> revA2 [dir=back, style="dashed"]
}
}}}

== Proposed Exchange Algorithms ==

  1. Push will inspect incoming draft-phase heads from the server. If any are
  dead locally, we push their kill marker to the server.

  We would exchange (pull or push):
    a. markers that apply to changesets being exchanged
    a. kill markers for ctx in common post-exchange

  1. We push `[$NODE:↓:killed(heads(descendents($NODE)))]`