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

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 19/04/14 00:54, Trevor Perrin wrote:
> 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).

If we're aiming to support linear conversations rather than threaded
conversations, we may need even less information than that. We can
model a linear conversation as a series of instants, with one or more
messages per instant; messages that occur in the same instant are
considered simultaneous. (There are no empty instants - each instant
lasts until somebody speaks.)

To display such a conversation, we need some way to indicate that A
follows B, and some way to indicate that A and B are simultaneous. We
don't need threads or nesting. If we use Tom's side-by-side display,
we don't need the second, more complex diagram; the first diagram
(possibly with more than two messages side-by-side) is all we need.

To represent such a conversation at the protocol layer we can either
use pointers (i.e. hashes) or counters. If we use pointers, each
message points to the latest message displayed by its sender, where
the latest message is the one with the longest chain of predecessor
pointers back to the root. Messages with predecessor chains of the
same length are simultaneous. Messages that point to not-yet-received
messages have arrived early and aren't displayed yet.

If we use counters, we don't need vector clocks - a Lamport clock is
sufficient. The first message has timestamp 0, and each subsequent
message has a timestamp one greater than the highest timestamp
displayed by its sender. Messages with the same timestamp are
simultaneous. Messages with timestamps more than one greater than the
highest timestamp displayed so far have arrived early and aren't
displayed yet.

Both these representations allow an attacker to insert messages into
the past, but those messages will be shown as simultaneous with other
messages - it isn't possible to insert a message between two existing
messages, or between an existing message and an anticipated message,
without a collision being displayed. Maybe that's sufficient to
prevent the ice cream attack... I guess it depends on how people
interpret collisions.

Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTU/qOAAoJEBEET9GfxSfM1AcIAMUcLCqRCX9L+UHD6oPvAN+q
mMa76xN1Sr3d3qFyinRP5mV+kr7U/dahh99PnWBcJoiiUXq/JbJsFxhsx6sx2vgR
KbLMNHvcLHtMF8dvGJR8GzjxE3J3fmzdLvmppAKne4tlVm1hLDaRoiKDQYN8xhK4
uZlRIRXHZd54hJgS6Z7j7W19WKQSvzRjfckkpYrzWWl/9lCOMhyXnwsLq/hAyswS
l2oT5cS3z/kOxl0T02IayBO8kKsgC7Pu71XBCF1FOVsg3KqqYGwxe57DpjJwtu7U
zacm6M7IPRFoi4qQYIXh/XH8eJXU/XeeupiO5+HzBieDNci4+Li6h9L7ajLcooE=
=YCZZ
-----END PGP SIGNATURE-----