3 ms·

Ok, let's think: if a single client only has ordering locally and the server assigns global ordering, than retransmit in case a client didn't receive an acknowl

Ok, let's think: if a single client only has ordering locally and the server assigns global ordering, than retransmit in case a client didn't receive an acknowledgement from the server is going to assign global ordering again, like it's a new batch of data. Which breaks consistency. If we want to keep consistency and be able to synchronize we need to have this global ordering on the client. To make it work that way a client has to ask the server for a starting point before it can generate operations and increment it with each new operation. But then it doesn't sound like the server does the ordering and starts to look a lot like lamport timestamps.

burntsushi 9y ago
Maybe think about this way: a client has two sets of operations. One set reflects what it has received from the server and the other set reflects the operations that the client itself has generated, but has not yet received confirmation from the server that they have been assimilated into a global ordering (or perhaps the client simply hasn't sent them yet). We also have a guarantee that if a client sends a batch of operations, then the server will not reorder those operations relative to one another. For the client, the only real choice they have (until they hear otherwise) is to assume that all local operations come after all server operations. At some point, the server will send the client updates with new operations from other clients, or perhaps even confirmation that some of their previously local operations have now been recorded by the server and assigned a total ordering. The client is then responsible for updating its local state: moving the local operations into the server operation list and updating the server operation list to contain any additional operations reported by the server. The client must then re-materialize any data structures dependent on these operations, but depending on the nature of your operations, this might be possible to do efficiently. Given enough time where every client is idle, its set of local operations will become empty as they all move into the server's set of operations. All clients then have the same set of operations in the same order, which gives you consistency.
- zzzcpan 9y ago
  Well, communications are still unreliable and you really have to use proper distributed algorithms to solve that if you want to keep consistency, there is no way around it.
  - burntsushi 9y ago
    It seems like a pretty simple solution works in this particular design space: the client keeps asking for updates and keeps pushing updates to the central server.
    - zzzcpan 9y ago
      I think we are talking past each other. It is simple to synchronize things, very simple, but only without centralized coordination. In distributed systems any coordination complicates things a lot and I don't think it's even possible to make simpler solution with coordination if there exists one without it.

burntsushi 9y ago

Maybe think about this way: a client has two sets of operations. One set reflects what it has received from the server and the other set reflects the operations that the client itself has generated, but has not yet received confirmation from the server that they have been assimilated into a global ordering (or perhaps the client simply hasn't sent them yet). We also have a guarantee that if a client sends a batch of operations, then the server will not reorder those operations relative to one another. For the client, the only real choice they have (until they hear otherwise) is to assume that all local operations come after all server operations. At some point, the server will send the client updates with new operations from other clients, or perhaps even confirmation that some of their previously local operations have now been recorded by the server and assigned a total ordering. The client is then responsible for updating its local state: moving the local operations into the server operation list and updating the server operation list to contain any additional operations reported by the server. The client must then re-materialize any data structures dependent on these operations, but depending on the nature of your operations, this might be possible to do efficiently. Given enough time where every client is idle, its set of local operations will become empty as they all move into the server's set of operations. All clients then have the same set of operations in the same order, which gives you consistency.

zzzcpan 9y ago
Well, communications are still unreliable and you really have to use proper distributed algorithms to solve that if you want to keep consistency, there is no way around it.
- burntsushi 9y ago
  It seems like a pretty simple solution works in this particular design space: the client keeps asking for updates and keeps pushing updates to the central server.
  - zzzcpan 9y ago
    I think we are talking past each other. It is simple to synchronize things, very simple, but only without centralized coordination. In distributed systems any coordination complicates things a lot and I don't think it's even possible to make simpler solution with coordination if there exists one without it.