-----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----- _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
