3 ms·

I think I've done a bad job at communicating my design because it's perfectly consistent with what you've said. My proposed design is a client/server model, but

I think I've done a bad job at communicating my design because it's perfectly consistent with what you've said. My proposed design is a client/server model, but that doesn't mean it isn't distributed. Each client can still operate on its own for as long as it wants, and it chooses to synchronize with the central server whenever it likes. (In fact, this is quite similar to most peoples' workflows with Git/Github, and I certainly wouldn't call that painful.) In any case, thanks for the pointers about the Microsoft research. I don't think I've seen that. I'll check it out.

naasking 9y ago
See here for a comprehensive review of CR: http://lambda-the-ultimate.org/node/4699 http://lambda-the-ultimate.org/node/4699 Each client can operate on its own what though? If they have some kind of private copy of the data, then how do you resolve conflicts? CRDTs are about doing this automatically by restricting the types of changes clients can make. Concurrent revisions permit arbitrary changes so long as you provide a merge function to make them commute. I think you're just hand-waving a lot of the complexity away by using "synchronize" without explaining what is synchronized and how. That's where all the complexity in distributed computation stems from.
- burntsushi 9y ago
  > Each client can operate on its own what though? Imagine the fundamental representation of your data structure is a sequence of operations. From those operations, you can generate your model. A really simple application of this is a graph, which is just a set of vertices and edges. So if you have these operations VertexAdd { id: fooID, label: foo } VertexAdd { id: barID, label: bar } VertexAdd { id: quuxID, label: quux } EdgeAdd { src: fooID, dst: quuxID } where the ids generated are unique (say, uuids). The corresponding model is just the graph: Graph { vertices: {foo, bar, quux}, edges: {{foo, bar}}, } You might imagine operations to remove vertices and edges as well. Many operations are commutative (add vertex), but some pairs of operations don't commute, e.g., add vertex/remove vertex. As I understand that, that's the central problem this paper is trying to address via CRDTs. What I'm saying is that the total ordering imposed by the server makes this concern moot, because the server always picks one sequential ordering. Let's say there are multiple simultaneous clients editing our graph structure above at the same time. Let's consider an example of a pair of operations that commute. One of them decides to remove vertex quux while the other adds an edge that connects quux to foo: client1: VertexDelete { id: quuxID } client2: EdgeAdd { src: quuxID, dst: fooID } If both clients attempt to update the server with these new operations, then the server will declare one ordering as true and send the resulting operations back to the clients with the correct ordering. The clients must then adjust. In this case, the outcome is the same regardless of the ordering chosen (because you can't draw an edge to a vertex that doesn't exist). What about the case when two operations are not commutative? Well, that means they are dependent, which in turn means that every client receives them in the order in which they were applied. An add/delete vertex is one such example, because the client doing the delete must acquire a vertex ID to give to the VertexDelete operation, but the only way to acquire the ID is to observer the VertexAdd first. Another example of dependent operations is attaching meta data to vertices, e.g., client1: VertexAdd { id: anotherID, label: Another } VertexLabel { id: anotherID, label: Changed } In this case, VertexAdd/VertexLabel are dependent, but the Label operation requires the vertex ID. Now of course, clients can misbehave. There's no reason why a client couldn't generate the ID and add operations in this order: client1: VertexLabel { id: anotherID, label: Changed } VertexAdd { id: anotherID, label: Another } But if we can assume well behaving clients, then this should be OK! And even if clients are misbehaving, then the process of turning the operations into a model can simply drop operations like VertexLabel because they reference a vertex that doesn't exist.
  - naasking 9y ago
    > If both clients attempt to update the server with these new operations, then the server will declare one ordering as true and send the resulting operations back to the clients with the correct ordering. The clients must then adjust. But this seems no different than "last write wins". The point is that clients want to keep reliably working on their copy without suddenly losing all of their work because of an incorrect/stale assumption that their changes would be accepted. This is typically considered undesirable. So with non-commutative changes, either you would sync with the server after each change to ensure you can make meaningful progress, or you risk doing lots of meaningless work and having it all undone.
    - burntsushi 9y ago
      Yes, but that's natural conflict. One client can do something that the other client doesn't like, and they can go back and forth. The system can't prevent that because it's a natural part of collaboration. And note that this only applies to the interactions between local operations and server operations. If a client does a bunch of local work and only a small component of it is tied to a previous operation (e.g., one edge in graph), then that doesn't mean the rest of the work gets dropped. That is, if I create a bunch of new vertexes and edges, and only one of those edges connects my new vertex to a vertex already present in the server's operations and that connection is deleted simultaneously by another client, then I don't lose all of my work---I just lose that one edge. The rest of my graph is in tact. And of course, if this is an end user application (like, say, Google Docs), then the user should be able to view the history and undo what their collaborator did. But I don't see this as any different than editing a document on Google Docs where one collaborator keeps deleting stuff you did.
      - naasking 9y ago
        > Yes, but that's natural conflict. One client can do something that the other client doesn't like, and they can go back and forth. The system can't prevent that because it's a natural part of collaboration. But this isn't necessarily true. The point is there's more concurrency and collaboration possible than what you describe, if you restrict the operations in specific ways. This is what CRDTs and CRs do. > But I don't see this as any different than editing a document on Google Docs where one collaborator keeps deleting stuff you did. It is different. The collaborator actually saw your changes and decided to remove them. This is very different than your changes arbitrarily being lost by the system itself because its merge behaviour is insufficient.

naasking 9y ago

See here for a comprehensive review of CR: http://lambda-the-ultimate.org/node/4699 http://lambda-the-ultimate.org/node/4699 Each client can operate on its own what though? If they have some kind of private copy of the data, then how do you resolve conflicts? CRDTs are about doing this automatically by restricting the types of changes clients can make. Concurrent revisions permit arbitrary changes so long as you provide a merge function to make them commute. I think you're just hand-waving a lot of the complexity away by using "synchronize" without explaining what is synchronized and how. That's where all the complexity in distributed computation stems from.

burntsushi 9y ago
> Each client can operate on its own what though? Imagine the fundamental representation of your data structure is a sequence of operations. From those operations, you can generate your model. A really simple application of this is a graph, which is just a set of vertices and edges. So if you have these operations VertexAdd { id: fooID, label: foo } VertexAdd { id: barID, label: bar } VertexAdd { id: quuxID, label: quux } EdgeAdd { src: fooID, dst: quuxID } where the ids generated are unique (say, uuids). The corresponding model is just the graph: Graph { vertices: {foo, bar, quux}, edges: {{foo, bar}}, } You might imagine operations to remove vertices and edges as well. Many operations are commutative (add vertex), but some pairs of operations don't commute, e.g., add vertex/remove vertex. As I understand that, that's the central problem this paper is trying to address via CRDTs. What I'm saying is that the total ordering imposed by the server makes this concern moot, because the server always picks one sequential ordering. Let's say there are multiple simultaneous clients editing our graph structure above at the same time. Let's consider an example of a pair of operations that commute. One of them decides to remove vertex quux while the other adds an edge that connects quux to foo: client1: VertexDelete { id: quuxID } client2: EdgeAdd { src: quuxID, dst: fooID } If both clients attempt to update the server with these new operations, then the server will declare one ordering as true and send the resulting operations back to the clients with the correct ordering. The clients must then adjust. In this case, the outcome is the same regardless of the ordering chosen (because you can't draw an edge to a vertex that doesn't exist). What about the case when two operations are not commutative? Well, that means they are dependent, which in turn means that every client receives them in the order in which they were applied. An add/delete vertex is one such example, because the client doing the delete must acquire a vertex ID to give to the VertexDelete operation, but the only way to acquire the ID is to observer the VertexAdd first. Another example of dependent operations is attaching meta data to vertices, e.g., client1: VertexAdd { id: anotherID, label: Another } VertexLabel { id: anotherID, label: Changed } In this case, VertexAdd/VertexLabel are dependent, but the Label operation requires the vertex ID. Now of course, clients can misbehave. There's no reason why a client couldn't generate the ID and add operations in this order: client1: VertexLabel { id: anotherID, label: Changed } VertexAdd { id: anotherID, label: Another } But if we can assume well behaving clients, then this should be OK! And even if clients are misbehaving, then the process of turning the operations into a model can simply drop operations like VertexLabel because they reference a vertex that doesn't exist.
- naasking 9y ago
  > If both clients attempt to update the server with these new operations, then the server will declare one ordering as true and send the resulting operations back to the clients with the correct ordering. The clients must then adjust. But this seems no different than "last write wins". The point is that clients want to keep reliably working on their copy without suddenly losing all of their work because of an incorrect/stale assumption that their changes would be accepted. This is typically considered undesirable. So with non-commutative changes, either you would sync with the server after each change to ensure you can make meaningful progress, or you risk doing lots of meaningless work and having it all undone.
  - burntsushi 9y ago
    Yes, but that's natural conflict. One client can do something that the other client doesn't like, and they can go back and forth. The system can't prevent that because it's a natural part of collaboration. And note that this only applies to the interactions between local operations and server operations. If a client does a bunch of local work and only a small component of it is tied to a previous operation (e.g., one edge in graph), then that doesn't mean the rest of the work gets dropped. That is, if I create a bunch of new vertexes and edges, and only one of those edges connects my new vertex to a vertex already present in the server's operations and that connection is deleted simultaneously by another client, then I don't lose all of my work---I just lose that one edge. The rest of my graph is in tact. And of course, if this is an end user application (like, say, Google Docs), then the user should be able to view the history and undo what their collaborator did. But I don't see this as any different than editing a document on Google Docs where one collaborator keeps deleting stuff you did.
    - naasking 9y ago
      > Yes, but that's natural conflict. One client can do something that the other client doesn't like, and they can go back and forth. The system can't prevent that because it's a natural part of collaboration. But this isn't necessarily true. The point is there's more concurrency and collaboration possible than what you describe, if you restrict the operations in specific ways. This is what CRDTs and CRs do. > But I don't see this as any different than editing a document on Google Docs where one collaborator keeps deleting stuff you did. It is different. The collaborator actually saw your changes and decided to remove them. This is very different than your changes arbitrarily being lost by the system itself because its merge behaviour is insufficient.