> Say 100 nodes edit a doc. To drop a tombstone, without a central server we need 99 acks. Even with a server, the server keeps an ever-growing list of ops unless it uses some garbage collection techniques. And as stated by OP those techniques have their own problems.
Here's how it could be done (very roughly):
When a client makes a modification, it creates an op representing that modification and includes a list of server identifiers to send the op to. Then queues the op. Once op is sent and ACKed by at least one of the servers the op is dropped from the queue.
Servers receiving the op synchronize the op with each other, ACKing each other and removing ACKed servers from the list. They also synchronize with the clients, sending the op to each client and asking clients to ACK to all servers. Obviously there are multiple ways to do it and it can be almost as efficient as theoretically possibly, but of course you can't avoid some metadata for each client associated with a particular document even though it doesn't have to be kept in server memory, it could be stored on disk.
> I'm talking about structures with semantic meaning.
Semantic meaning generally doesn't map to any data structure directly, CRDTs are not an exception here either.
Here's how it could be done (very roughly):
When a client makes a modification, it creates an op representing that modification and includes a list of server identifiers to send the op to. Then queues the op. Once op is sent and ACKed by at least one of the servers the op is dropped from the queue.
Servers receiving the op synchronize the op with each other, ACKing each other and removing ACKed servers from the list. They also synchronize with the clients, sending the op to each client and asking clients to ACK to all servers. Obviously there are multiple ways to do it and it can be almost as efficient as theoretically possibly, but of course you can't avoid some metadata for each client associated with a particular document even though it doesn't have to be kept in server memory, it could be stored on disk.
> I'm talking about structures with semantic meaning.
Semantic meaning generally doesn't map to any data structure directly, CRDTs are not an exception here either.