I am thinking about an interesting problem right now.
Suppose I have a DAG of objects. Every object contains three data points:
* A list of parents (via Content-address hashes)
* A pointer to some content (almost irrelevant for this thought process)
* A version number (irrelevant for this thought process)
I have a limited but unknown number of peers that are allowed to "post" to that DAG. Once a peer discovers that another node has posted to the DAG, they either fast-foward or merge (which is trivial here) and go on.
All peers gossip all the time, so fast-forwarding is expected to be the "normal case" when all peers are online - but in case of network split there is no issue.
Now, suppose I want to allow "rewriting" the DAG.
That means, one node decides that deep down in the DAG, they want to change a node. That would change all other nodes that come after it.
How would the other peers know that the node was rewritten?
Two ideas:
* All peers keep track of "this other peer points to this hash right now". Once a peer rewrites their DAG, other peers can see that rather easily. That would involve some tricky logic, but I guess would be possible 🤔 The other peers can then update their stuff to that new DAG (and if needed even "rebase" changes that they have done between the rewrite and now, if there was a network split during that time)
* The second option would involve adding timestamps to the DAG nodes, so other nodes can see that a portion of the DAG was rewritten
The second option would add more fields to the DAG nodes, which I would like to not do, because they should be as light as possible.
What do you think? :boost_ok:
#algorithms #softwaredevelopment #dag #distributedsystems #graphdata #datatypes