Eventual consistency

Brief

Since community events are distributed independently in a P2P Waku network, the state of the community on certain nodes may differ, which is to be expected. However, we must ensure eventual consistency, meaning that all nodes should reflect the same community state if they possess the same set of events (we assume that all nodes will eventually receive all events). Furthermore, the order in which event messages are processed by a control node should not dictate the final state. We address the first concern by sorting events on the receiver side by their timestamps and applying them sequentially to the latest CommunityDescription.

Issue

We lack a mechanism that is resistant to messages being processed out of order by the control node. This is because the control node applies events immediately and rejects those that arrive later. Let's consider following scenario:

AdminA accepts request to joinmsgA: e1: accept
AdminA rejects request to join msgB: e1: accept e2: reject

Expected result is user being rejected from the community.

There have been a few approaches investigated.

		in order (msgA,msgB)	out of order(msgB,msgA)	consistency
A	reject	accepted	rejected	✕
B	reject/re-apply (as we have now)	rejected	accepted	✕
C	reject/re-apply + lamport timestamp per event type	rejected	rejected	✓
D	reject + notification	accepted	accepted/rejected (depending on user action)	✓/✕

Option A - not ok, the result depends on the order of the messages
Option B (that’s what we currently have) - not ok, the result depends on the order of the messages
Option C - ok, the result is eventually consistent
Option D - ok, but requires manual action from member (notification about change being not accepted)

Let’s deep dive into option C.

cdc: CommunityDescription clock on which events are applied

e1..en: events

e1c..enc: events’ clock