Issues with odd/even undo/redo counters in CRDTs

A commonly suggested technique to implement undo/redo in CRDT-based editors is to use a counter for each operation which is initialized with 0. When the user undoes an operation, this counter is incremented by 1. For redoing, the same counter is incremented by 1 again. If the counter is odd, the operation is considered undone, otherwise it is applied normally.

To solve the problem of concurrent undos of the same operation, a simple conflict resolution strategy is used: highest-counter-wins.

In this post, I'll provide a small example which shows the problem and then one alternative way which solves the problem.

Motivation: a pathologic example🔗

Let's assume that we have this document:

hello world

If we have two users, u_0 and u_1, and u_0 replaces "world" with "universe" in op_22. This change gets propagated to both u_0 and u_1, so they both see:

hello universe

u_1 wants to see what there was before and undoes the operation, sees the previous state and then redoes it. The operations generated by this are undo(u_1, op_22) and redo(u_1, op_22).

Concurrently (e.g. because the user is offline) u_0 decides that the initial version was better and undoes op_22: undo(u_0, op_22). In the counter model these operations result in this:

u_0 edits: set_undo_counter(op_22, 1), set_undo_counter(op_22, 2)
u_1 edits: set_undo_counter(op_22, 1)

Because of the highest-counter-wins strategy, this results in the counter being 2. As 2 is even, the operation ends up not being undone.

This is bad as u_1's intention is completely ignored. However, there exists an ordering of the undo/redo operations which produces a consistent result which respects both user's intentions: if we apply u_0's undo & redo first and u_1's undo after,

Approach: voting🔗

Not working: simple voting🔗

A simple model which fixes the pathology in the motivation is voting: Every edit has a counter which is initialized to 0 and for undoing, a user adds -1 to it, whereas for redoing +1 is added. If the counter is negative, the operation is treated as undone. By adding up the operations, we will correctly undo the operation in the example.

However, this approach does not work correctly when we have an operation which is concurrently undone in two places -> the counter is -2 and a user who has received both undos both wants to redo the operation. By just adding +1, we still end up with a counter value of -1, which means the operation stays undone.

Fixed: dynamic voting🔗

To fix this, we add as much as is needed to make the counter the value we want it to be. E.g. if the current counter value is -2 and a user wants to redo the operation, it adds +2.

Preventing overflows🔗

Unless we have an unbounded integer for the counter, there can be overflows as the counter value grows whenever two users concurrently decide to undo or redo an operation.

To avoid running out of bits, we can add a generation counter, which is initialized at 0 and kep track of in addition to the main undo/redo-counter. Whenever the integere type we have chosen for the main undo counter saturates, a user will send its operation with an increased generation counter and either +1 or -1 for whatever the operation was that it wanted to do.

A higher generation will suppress all undo/redo operations for the previous generation.

Obviously this is suboptimal as all undos/redos of users for whom the counter did not saturate (e.g. because of a different order of arrival) will be lost. In these cases we wolud regress to a situation which is as bad as the odd/even counters. However, as this should be rare in well-synced environments, I believe this is a worthwhile trade-off to allow better intention preservation in the majority of cases.

Other applications: checkboxes🔗

We can use the same approach for checkbox ticked-ness. It then allows a user to check and uncheck a checkbox without affecting other users (unless the other users act on the in-between state).