[messaging] Minimal requirements for group chat

[Michael Rogers]

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

On 16/04/14 16:36, Michael Rogers wrote:
> If a member receives a message with the same sequence number as a 
> staged message, she sends a nack to every other member and
> discards both messages. Anyone who receives a nack for a staged
> message discards the message, except the author, who unstages the
> message. If two or more authors try to send messages with the same
> sequence number, every colliding message will be nacked by at least
> one member, unstaged by its author and discarded by everyone else,
> and the sequence number will remain unused. Each author waits for a
> random interval and then resends her message with an incremented 
> retransmission counter and the first unused sequence number, which
> may be the same as before, or higher if another message has been
> committed in the meantime.

A more efficient way to handle collisions: define some transitive way
to choose between two messages with the same sequence number (e.g.
hash the sequence number with the author's identity and sort by hash,
so each author takes precedence some of the time).

When a member receives a message with sequence number i, where i > the
highest committed sequence number, she tries to stage the message in
slot i. If the slot is empty, she stages the message and sends an ack
to every other member. Otherwise she compares the new message with the
staged message. If the old message wins, she increments the new
message's sequence number and tries to stage it in slot i+1. If the
new message wins, she stages the new message in slot i, sends an ack
to every other member, increments the old message's sequence number
and tries to stage it in slot i+1.

This variant doesn't require retransmissions or nacks. A message may
be acked by some but not all of the members in one or more rounds
before it's finally acked by everyone in the same round and committed.

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

iQEcBAEBCAAGBQJTTs0nAAoJEBEET9GfxSfMlDoIAI/ux+p/ma9lH8xz0Kk6thx3
4SYkS9sYQb7ta8/wRN3n4JR6iHI8zEDXrSyhBB/h0k3rFH8J4JkyZo1TPn+OC0nz
26XXK6MaW9s2Dz257TpM1FZyxa4ZbHdxmdvGTQOu9nXgtAumfRxNLFiaaValrI22
EMaPsWcBznmTn2e/lc+WulM39sFLtO8Zf7ACw0zet38t16/VkO4sN6UA8U8Zi8mA
x8FTyG7iipYqFigenrhMq9U8ttFbWVs97gUcWmy1kKZWgBkxRwzlNBE5LYEbInfJ
SZPv8/Z6UpFJu5GVrpw1i6bdDzRv84T4p6ysPlWu9rjSp6ybOWtQimHxOgcpxYk=
=P9Q0
-----END PGP SIGNATURE-----