16

I've started looking at approaches to data synchronisation among a set of peers. The peers must be able to work in a disconnected way and then synchronise together to merge their local changes.

Peers should be able to merge local updates with a "three way merge". So, at synchronisation peers should know which facts are more recent, but where there is no strict ordering, they should be able to merge together the facts based on the common root.

When independent peers make changes, they can "time stamp" them with a "clock". I use the term "clock" and "time stamp" but I'm not meaning a wall time clock. I mean some kind of partial ordering of events which makes causality clear. It's the "happened before" relationship among events that forms a directed acyclic graph (DAG).

It seems like the "usual" way to do build this partial ordering is by using a vector clock. These can become very large, however. More recent developments such as interval tree clocks provide more compact storage of time stamps.

What I'm not at all clear about is why synchronisation protocols apparently don't "simply" store the DAG explicitly. (Or do they?)

Peers can independently create a time stamp by randomly generating a UUID (or by other means, such as <peer-name> + <local-monotonically-increasing-counter>). The ordering of this time stamp is entirely clear to that peer.

When 2 peers sync to each other, they can agree on a new time stamp. Again, the ordering of this time stamp is clear to both peers.

There is now a requirement to pass the happened before DAG between peers, but the storage and bandwidth requirements of this are small. Time points are graph vertexes. As such they have 1 or 2 incoming edges (1 for an event on a client and 2 for a sync between clients). This is bounded and independent of the number of peers in the network.

To use an individual time point, you require the graph of time points that lead in to this. However, as far as I can see, any peer that is able to know of a time point (it has generated it itself, or generated it with another peer, or has been told it by another peer when synchronising with it) has also had an opportunity to know about the history leading up to that time point. I think there's probably an inductive proof for this.

Given that storing and synching the DAG explicitly seems simple: is this used in practice? If not, why are vector clocks preferred?

Notes

Peer to peer

I'd prefer to a peer to peer solution over a client server solution.

The likely end topology will be many clients connecting to a much smaller group of servers that replicate among themselves. However, it'd be nice to have a general solution that supported this particular topology rather than a solution that requires this specific topology.

Improve this question
4
  • I may be misunderstanding what you're saying, but it's unclear how a graph of all events leading to a state could be smaller than a vector of counters. Unless you're in a system that has an extremely large number of nodes and an extremely small number of changes.
    – kdgregory
    Commented Jun 10, 2015 at 10:50
  • Thanks @kdgregory – good point. To be able to compute a three way merge in the future, you need to know the past (and be able to determine the DAG of the past time points). So, if you are storing those past time points then explicitly storing the DAG is cheaper. If you are not storing those past time points then you can't compute a three way merge of data anyway. – I wonder if this three way requirement might be the thing? If you don't want 3-way, perhaps vector clocks better than explicit DAG?
    – Benjohn
    Commented Jun 10, 2015 at 11:02
  • I reckon this could be the crucial point @kdgregory, so I've added a bit about that to the question. I am assuming it be possible to perform a 3-way-merge, which also implies that all of history is known. If all history is known then (I reckon) an explicit DAG is cheaper. If history is truncated, then vector clocks are probably the less costly approach.
    – Benjohn
    Commented Jun 10, 2015 at 11:12
  • 1
    Yeah, my understanding of vector clocks is that they're intended simply for an accept/reject decision: "node C is trying to update this piece of data, but it isn't aware of node B's update".
    – kdgregory
    Commented Jun 10, 2015 at 11:16

4 Answers 4

Reset to default
2

As far as I can tell, version control systems like Git and Mercurial use the DAG approach rather than vector clocks.

Improve this answer
4
  • 1
    Without an explanation, this answer may become useless in case if someone else posts an opposite opinion. For example, if someone posts a claim like "Propversion control systems like Git and Mercurial use vector clocks rather than the DAG approach", how would this answer help reader to pick of two opposing opinions? Consider editing it into a better shape, to meet How to Answer quality standards.
    – gnat
    Commented Aug 12, 2016 at 21:30
  • 2
    The way I understood the question, they were asking if there are any real world examples of where DAG is used rather than vector clocks.
    – bikeman868
    Commented Aug 13, 2016 at 21:27
  • 1
    Both Git and Mecurial are real world examples of peer to peer change synchronization using DAG, and I hope that benjohn will find my answer helpful even though you voted it down.
    – bikeman868
    Commented Aug 13, 2016 at 21:30
  • Hi @bikeman868 I've voted you up for a net 0 (sorry). Your answer is helpful, even if couched with uncertainty! While references or authoritative answers are always nice, stack exchanges don't mandate that! Your suggestion makes good sense with points in comments on the question. It seems like when you want to store history and be able to merge histories, then a DAG is appropriate. When you don't store history and want synchronisation and consensus on the current state, then vector clocks are what you need.
    – Benjohn
    Commented Aug 21, 2016 at 11:31
2

Take a look on the consensus problem. Depending on your task requirements (as to how much data do you have, how many syncing nodes, how often etc.) existing solutions to that problem (like "Raft") might be suitable for your case.

Another (maybe tangential) approach to this problem is designing a CRDT.

Improve this answer
1
  • Braid HTTP is attempting to create a CRDT-based state sync protocol via augmenting HTTP. They have a great visualization of a Time DAG and Space DAG, and how these two concepts inter-relate to arrive at eventual consistency.
    – Duane J
    Commented Oct 25, 2019 at 7:07
1

I'm asking myself the same question, and just asked that question earlier today to the CS stackexchange. Here are some elements of answer with my current thought maturity:

DAG vs. vector clocks

What unifies them:

  • They both could be used to determine causality relation in a distributed system

Advantages of vector clocks:

  • Size of data to synchronize in vector clock grows with the number of replica, but not with the number of events; which in most real life application is more efficient. Also optimizing DAG data transfer between replica over the network may not be straightforward.

Advantage of DAGs:

  • Easier to conceptualize? And possibly implement?
  • Models the full tree, so wins over vector clocks when we want not only to understand if an event e1 occurred before another event e2, but want to access more details on the event present, possibly their content, etc.
  • More expressive than vector clocks because vector clocks DAGs are constructed with a specific algorithm that constrains the expressiveness, and there are things you cannot do, such as taking three or more previous events to build one new event (at least from my understanding of the original paper, but that limitation may be challenged)
Improve this answer
0

The Aleph protocol is a p2p leaderless protocol that builds a distributed DAG of sets of transactions (or events) by consensus

https://arxiv.org/pdf/1908.05156

Improve this answer
1
  • You should expand your answer to show how the referenced protocol addresses the points brought up by the original question. It is important to make answers self-sufficient, as this benefits everybody coming across this question.
    – BobDalgleish
    Commented Mar 16, 2020 at 16:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.