On Fri, Apr 18, 2014 at 2:32 PM, Alexandre Carmel-Veilleux <[email protected]> wrote: > > On Fri, Apr 18, 2014 at 5:07 PM, Tony Arcieri <[email protected]> wrote: >> >> On Fri, Apr 18, 2014 at 1:42 PM, Trevor Perrin <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
