[messaging] Group consistency with removal (was: Matrix.org)

[Trevor Perrin]

On Tue, Mar 10, 2015 at 4:51 PM, Matthew Hodgson <matthew at matrix.org> wrote:
>
> Correct - currently we don't allow removal.  In the scenario of room
> membership, we simply switch members' state to 'left' when they leave, so
> currently state accumulates increasingly over time.


I wonder if tracking old users is a good general way to handle removal?

To summarize the issue:

We've been discussing how to achieve a consistent view of group
membership when users in a group can be added and removed by multiple
group members.

I think the goal should be "eventual consistency".  Add/remove
messages might get lost or delayed.  This could cause users to have
different views of group membership, but I don't think that should
prevent users from sending or receiving messages (at least in
email/text-messaging protocols).

Still, it would be good to correct this quickly.

How to do this depends on the add/remove policy.  If the policy is
"anyone can add new members, no-one can remove or leave", it's easy
for every message to list its recipients, and for the recipients to
add new ones to their membership set.

Removal makes this more complicated.  A simple flood no longer works
because recipients can't tell whether differences are adds or
removals.


But I'm wondering if that's easy to fix, enabling a policy "anyone can
add or remove members":
 * Every message contains a positive and negative list - the positive
list contains current group members (aka the message recipients), and
the negative list contains old/removed members.
 * Each entry in either list has a timestamp of when the action
occurred (entry was initially added to the list), and a user will only
be in one list at most.
 * The recipient stores all entries in local positive/negative lists,
except only stores the most recently timestamped entry for each
username.

So the idea is that we're just flooding positive/negative lists
simultaneously, and letting the most recent action take precedence.

Anyways, just wondering if that might work, or if there's other simple
approaches without having to do Paxos or something...


Trevor