[messaging] Minimal requirements for group chat
michael at briarproject.org
Wed Apr 16 11:34:15 PDT 2014
-----BEGIN PGP SIGNED MESSAGE-----
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.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
-----END PGP SIGNATURE-----
More information about the Messaging