Guarantee convergence if peers' receive messages in different orders #5

ansuz commented 2024年01月23日 16:37:08 +01:00

Hello!

I've been drafting this PR to the webxdc docs for a while, which introduces different concepts for managing shared state in p2p systems and particularly webxdc. The main topic is CRDTs, which guarantee that all clients can compute the same final state once they receive the same set of updates, even if they're received them in different orders.

@hpk and I discussed referencing this app as a minimal example of how to accomplish this without needing to pull in a big library like Yjs. After taking a deeper look at the code, I don't think it guarantees convergence on the same state, though it's very close to being able to do so.

The state of any given pixel is set on every invocation of the update listener, but these aren't guaranteed to arrive in the same order for every recipient, which would cause states to diverge. Differing orders are particularly likely if one or more of two active users queue changes while offline.

I think that this could be mostly avoided by:

1. including an app-specific sequence number in each update, to be used as a Lamport Timestamps (always equal to one greater than the largest known timestamp)

2. adding another array to track the sequence number responsible for setting a particular pixel to its current value

3. checking whether the timestamp for a given pixel is more recent than that of its current pixel before setting a value, and leaving it as-is if the update is older

...and because it's still possible for two users to set the same pixel to a different value with two updates that have equal timestamps

4. provide an additional deterministic method to break ties - Yjs uses randomly generated client ids, taking (I think) the lower integer

At first I thought that this was the intent of the current code when I saw its references to update.serial and update.max_serial when applying updates, but if I understand correctly this is only so that it doesn't do a complete redraw of the UI for every internal state change. In any case, @hpk indicated that those two values are set by the local webxdc provider to track the order in which they were received, which makes them unsuitable for my proposed usage.

Anyway, this is a cool app! Assuming I'm not overlooking something and my assessment is correct, I'll be happy to try submitting a PR implementing what I've proposed, or we can chat about different strategies for resolution.

Hello! I've been drafting [this PR to the webxdc docs](https://github.com/webxdc/webxdc_docs/pull/88) for a while, which introduces different concepts for managing shared state in p2p systems and particularly webxdc. The main topic is CRDTs, which guarantee that all clients can compute the same final state once they receive the same set of updates, even if they're received them in different orders. @hpk and I discussed referencing this app as a minimal example of how to accomplish this without needing to pull in a big library like Yjs. After taking a deeper look at the code, I don't think it guarantees convergence on the same state, though it's very close to being able to do so. The state of any given pixel is set [on every invocation of the update listener](https://codeberg.org/webxdc/pixel/src/commit/6c113ff8a6800a349b60bf242377ea6daf763396/script.js#L58), but these aren't guaranteed to arrive in the same order for every recipient, which would cause states to diverge. Differing orders are particularly likely if one or more of two active users queue changes while offline. I think that this could be mostly avoided by: 1. including an app-specific sequence number in each update, to be used as a [Lamport Timestamps](https://en.wikipedia.org/wiki/Lamport_timestamp) (always equal to one greater than the largest known timestamp) 2. adding another array to track the sequence number responsible for setting a particular pixel to its current value 3. checking whether the timestamp for a given pixel is more recent than that of its current pixel before setting a value, and leaving it as-is if the update is older ...and because it's still possible for two users to set the same pixel to a different value with two updates that have equal timestamps 4. provide an additional deterministic method to break ties - Yjs uses randomly generated client ids, taking (I think) the lower integer At first I thought that this was the intent of the current code when I saw its references to `update.serial` and `update.max_serial` [when applying updates](https://codeberg.org/webxdc/pixel/src/commit/6c113ff8a6800a349b60bf242377ea6daf763396/script.js#L59-L62), but if I understand correctly this is only so that it doesn't do a complete redraw of the UI for every internal state change. In any case, @hpk indicated that those two values are set by the local webxdc provider to track the order in which they were received, which makes them unsuitable for my proposed usage. Anyway, this is a cool app! Assuming I'm not overlooking something and my assessment is correct, I'll be happy to try submitting a PR implementing what I've proposed, or we can chat about different strategies for resolution.

WofWca commented 2024年01月23日 17:26:47 +01:00

One thing to keep in mind is that webxdc messages are not guaranteed to be delivered.

One thing to keep in mind is that [webxdc messages are not guaranteed to be delivered](https://docs.webxdc.org/faq/storage.html?highlight=deliver#are-application-updates-guaranteed-to-be-delivered-to-chat-peers).

link2xt commented 2024年01月23日 17:32:52 +01:00

Something simple like submitting last seen clock number incremented by 1 with every update and tracking clock number of each cell would be a nice PR, this would indeed help with reordering and is a clear improvement.

As for two users modifying the same pixel at the same time, they will most likely change it to the same value anyway as you can only flip between enabled/disabled, so maybe implementing this is an overkill that will only complicate the code.

Non-delivered messages are not a big deal for LWW, eventually it will converge once there are no losses. I would not implement gossiping changes on WebXDC level, improving deliverability is better done on the messenger level so everyone benefits from it.

Something simple like submitting last seen clock number incremented by 1 with every update and tracking clock number of each cell would be a nice PR, this would indeed help with reordering and is a clear improvement. As for two users modifying the same pixel at the same time, they will most likely change it to the same value anyway as you can only flip between enabled/disabled, so maybe implementing this is an overkill that will only complicate the code. Non-delivered messages are not a big deal for LWW, eventually it will converge once there are no losses. I would not implement gossiping changes on WebXDC level, improving deliverability is better done on the messenger level so everyone benefits from it.

ansuz commented 2024年01月30日 15:32:45 +01:00

I just submitted a PR demonstrating the basic idea I proposed.

I think it could be improved, but I wanted to convey the scope of the changes required before proceeding further so that you could decide whether it's a welcome contribution.

I agree that it's not particularly likely that peers will encounter noticeable/egregious bugs in the current implementation. My reasoning is more that overall structure of the app makes it a fairly good starting point for more complex features.

For example, it would be relatively easy (and possibly interesting) for someone to add a hard-coded color palette or full-range color-picker, allowing users to send arbitrary color information in updates rather than the current on/off behaviour. In such cases, conflicts or diverging states would be more likely to occur and possibly more visible if/when they did.

I'm not particularly concerned or interested in detecting dropped messages and recovering from them with gossip, as I think that's probably something that is more appropriately managed by the webxdc host platform. That said, under such cases where messages were delivered via gossip the proposed method should handle diverging update order more gracefully.

In any case, I understand if the added complexity of providing logical timestamps is beyond the scope of what you want this app to do. If that's the case I might just go ahead with implementing a color palette in a fork and instead propose that as a demonstration of principles discussed in the webxdc docs.

I just submitted [a PR](https://codeberg.org/webxdc/pixel/pulls/6) demonstrating the basic idea I proposed. I think it could be improved, but I wanted to convey the scope of the changes required before proceeding further so that you could decide whether it's a welcome contribution. I agree that it's not particularly likely that peers will encounter noticeable/egregious bugs in the current implementation. My reasoning is more that overall structure of the app makes it a fairly good starting point for more complex features. For example, it would be relatively easy (and possibly interesting) for someone to add a hard-coded color palette or full-range color-picker, allowing users to send arbitrary color information in updates rather than the current on/off behaviour. In such cases, conflicts or diverging states would be more likely to occur and possibly more visible if/when they did. I'm not particularly concerned or interested in detecting dropped messages and recovering from them with gossip, as I think that's probably something that is more appropriately managed by the webxdc host platform. That said, under such cases where messages were delivered via gossip the proposed method should handle diverging update order more gracefully. In any case, I understand if the added complexity of providing logical timestamps is beyond the scope of what you want this app to do. If that's the case I might just go ahead with implementing a color palette in a fork and instead propose that as a demonstration of principles discussed in the webxdc docs.

WofWca commented 2024年01月30日 19:30:45 +01:00

Non-delivered messages are not a big deal for LWW, eventually it will converge once there are no losses

LWW is "last write wins", right? Well, IMU this can only be said about one pixel, not the canvas as a whole. If one user changes one pixel and the update doesn't get delivered to some people, and then nobody ever touches that pixel again, the states will be diverged.

I said that because "does it make sense to worry about conflict resolution if we can't even guarantee to sync the list of updates". I have a feeling that missing a message is more likely than getting a conflict, at least for this particular app.

> Non-delivered messages are not a big deal for LWW, eventually it will converge once there are no losses LWW is "last write wins", right? Well, IMU this can only be said about one pixel, not the canvas as a whole. If one user changes one pixel and the update doesn't get delivered to some people, and then nobody ever touches that pixel again, the states will be diverged. I said that because "does it make sense to worry about conflict resolution if we can't even guarantee to sync the list of updates". I have a feeling that missing a message is more likely than getting a conflict, at least for this particular app.

ansuz commented 2024年01月30日 21:40:23 +01:00

I said that because "does it make sense to worry about conflict resolution if we can't even guarantee to sync the list of updates". I have a feeling that missing a message is more likely than getting a conflict, at least for this particular app.

For the moment I'm only looking to guarantee convergence under the condition that everyone has the same set of messages, regardless of the order in which they were received.

You're right that having different sets of messages may produce differing results. That said, even with a mechanism to resend missing messages, a method to apply them in a consistent order (like what I'm proposing) will still be required for convergence.

I think it's sensible to consider these two separate problems, and to consider yours a strictly more difficult one which depends on mine being solved first.

> I said that because "does it make sense to worry about conflict resolution if we can't even guarantee to sync the list of updates". I have a feeling that missing a message is more likely than getting a conflict, at least for this particular app. For the moment I'm only looking to guarantee convergence under the condition that everyone has the same set of messages, regardless of the order in which they were received. You're right that having different sets of messages may produce differing results. That said, even with a mechanism to resend missing messages, a method to apply them in a consistent order (like what I'm proposing) will still be required for convergence. I think it's sensible to consider these two separate problems, and to consider yours a strictly more difficult one which depends on mine being solved first.

hpk commented 2024年02月11日 19:47:47 +01:00

thanks ansuz for the #6 which is merged and thus this issue here can be closed.

thanks ansuz for the https://codeberg.org/webxdc/pixel/pulls/6 which is merged and thus this issue here can be closed.