[messaging] Minimal requirements for group chat

Michael Rogers michael at briarproject.org
Thu Apr 17 02:22:57 PDT 2014

Hash: SHA256

On 16/04/14 21:19, Ximin Luo wrote:
> There are consistency issues, when you allow a message to be taken 
> out-of-context by other members - i.e. when you allow message M to
> be placed strictly after message M0, when the sender of M had not
> seen M0 at the time of sending. This something that
> partial-ordering would automatically protect against.

There's no objective total ordering of the messages, so what I'm
aiming for is a total ordering that respects any objective ordering
relationships that exist (for example, if message X replies to message
Y, X comes after Y) and arrives at some arbitrary consensus about the
order of the other messages.

If I understand right, your partial ordering proposal aims to
represent any objective ordering relationships that exist and
deliberately leave the rest of the ordering unresolved. Both goals are
valuable for different use cases - for a chat UI, as opposed to a
threaded discussion UI, I think people would expect a total ordering.

> In your example "if the new message wins, she stages the new
> message in slot i, sends an ack to every other member". So what
> happens to the old message? Its sequence number has now increased
> from Alice's perspective, but nobody else knows about this?
> Everyone still has her previous ack (old message at sequence i).
> OTOH, if you re-ack the old message with the new sequence number,
> acks are no longer binding - there is always the possibility that
> "someone has a higher sequence number".

The idea was that each member might ack a message several times in
different slots, but the message wouldn't be committed until everyone
acked it in the same slot. But there are several problems with that
idea so I'm abandoning it.

> There's also the issue of latency. If you wait until a message is 
> acked, to display it, then you would be at-least-doubling the
> latency for every message, and much more in the case of conflicts
> (which are very likely, with increasing members). However, if you
> want to display the message immediately upon receipt, you would
> need to accept the possibility that they may need to be re-ordered
> and re-drawn later.

If we want everyone to agree on the ordering then we have to accept
that either there will be a delay before messages are displayed, or
messages may change order after being displayed.

My feeling is that a delay is less confusing than reordering, but I
guess that's something we should test.

> Granted, this is a problem for the partial-order scheme I'm doing 
> atm. Instead of re-ordering messages, I have flags that point to
> the real parents of a message. Which is not the most simple, but at
> least it retains correctness. (I imagine it'll look something like
> "Bob: hi there! [1] [2]" where [1] [2] are rollovers.)

Interesting idea - but I wonder whether we can find a solution that
looks and behaves like a centralised system.

Version: GnuPG v1.4.12 (GNU/Linux)


More information about the Messaging mailing list