[messaging] Message order in group chat (attempt at summary)

[Trevor Perrin]

On Fri, Apr 18, 2014 at 2:32 PM, Alexandre Carmel-Veilleux
<acv at miniguru.ca> wrote:
>
> On Fri, Apr 18, 2014 at 5:07 PM, Tony Arcieri <bascule at gmail.com> wrote:
>>
>> On Fri, Apr 18, 2014 at 1:42 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>>
>>>  (1) It seems feasible to put messages into a causal/partial order by
>>> having them piggyback references and hashes to their parents (aka
>>> "causal predecessors").
>>
>>
>> I think that vector clocks (which wouldn't necessarily refer to previous
>> messages, perhaps just message counts since joining a conversation) are the
>> best bet at getting a realistic *partial* (not total) ordering of events
>
>
> And Interval Tree Clocks should be able to handle join and parts as well.

Aren't those algorithms more general than we need?  I think they're
designed to track causal order when messages can be exchanged between
individual entities.  But we're looking at chat protocols where every
message is broadcast to the entire chat.

In this case, I think it's sufficient for each message to declare its
immediate predecessors (Ximin first pointed this out to me).

There might be advantages to piggybacking information about the
complete set of predecessors, however.  That way, a recipient who
receives a message before all its predecessors have arrived knows the
entirety of what it's waiting for and could indicate missing messages
in the GUI, or request retransmission.

If we assume the message-stream from one participant to another is
ordered, conveying the complete set of predecessors could be
accomplished by piggybacking a vector of messages counts from each
participant.

---

To handle "join" and "part" events, I think we can assume these
actions are represented as messages which operate on the "member-set"
each participant recognizes.  The question Ximin has thought about
earlier is how to handle "merging" partially-ordered changes to the
member-set

I don't know if we have a good answer to that yet, but it seems like a
good question.

Trevor