Software Engineering
graph synchronization
Updated Sun, 21 Aug 2022 23:29:58 GMT

# How to resolve data-binding efficiently

Following this question, the solution to resolve data binding is to use DFS and Topological Sorting. I am not really sure exactly what that means. Here is an animation that roughly demonstrates what I am considering.

Say we have a data binding model like this:

``````

``````

And then we change one field.

``````

``````

Then it propagates:

``````

``````

More...

``````

``````

...

``````

``````

``````

``````

``````

``````

``````

``````

Sometimes it encounters a recent update, as shown with . But it keeps going:

``````

``````

Now it has had no more changes, so it goes back into the unchanged state.

``````

``````

So in this process, there are a few things:

1. All the nodes go into a "changed" state, until all nodes have been changed.
2. Somehow it figures out that all nodes that will be changed have been changed. This allows it to go back into the "unchanged" state.

This graph is pretty simplified because in reality there could be many complicated cycles and many more bindings per node.

However, given that the arrows indicate the direction in this Directed Cyclic Graph, I am wondering how this algorithm can efficiently perform this update propagation.

The nave approach would iterate through all of the nodes that have changed each step, to see if there is anything left to change. Maybe there is a third state, "changed and no more propagation". Once everything is in that third state (by checking every node every step), then it would be done. Wondering if there is an efficient way to accomplish this, so it doesn't need to iterate through every node each step somehow.

Also, it is possible that multiple values are changed at once, so it should be able to handle that as well, i.e.:

``````

``````

## Solution

This is either fundamentally meaningless or you've left out an important detail.

Your diagrams give each node 3 states:

Unchanged, don't propagate
Just now changed and in need of propagation
Old change, don't propagate

But in the end it all goes back to unchanged. So nothing is learned.

Which makes me think it's not really the same state as we started. It's just considered the same as far as propagation is concerned.

Which means that and are really the same state: don't propagate.

But you've chosen to give us a 4th state recent update which gets destroyed in this example.

All of which adds up to me thinking your symbols are just messed up.

Try it like this:

``````            0

0  0  0  0   0  0

0  0  0  0  0

0       0  0  0

0   0

0
``````

And then we change one field.

``````            0

0  0  0  0   0  0

1  0  0  0  0

0       0  0  0

0   0

0
``````

Then it propagates:

``````            0

0  0  1  0   0  0

1  1  0  0  0

1       0  0  0

0   0

0
``````

More...

``````            0

0  0  1  1   0  0

1  1  1  0  0

1       0  0  0

0   0

0
``````

...

``````            0

0  0  1  1   1  0

1  1  1  0  0

1       1  0  0

0   0

0
``````

``````            0

0  0  1  1   1  0

1  1  1  0  0

1       1  1  0

1   0

0
``````

``````            0

0  0  1  1   1  0

1  1  1  1  0

1       1  1  0

1   1

0
``````

Sometimes it encounters a recent update, as shown with 2.

``````            0

0  0  1  1   1  0

1  1  1  2  1

1       1  1  0

1   1

0
``````

But it keeps going:

``````            0

0  0  1  1   1  0

1  1  2  2  2

1       1  1  0

1   1

0
``````

``````            0

0  0  1  1   2  0

1  1  2  2  2

1       2  2  0

2   2

0
``````

Now it has had no more changes, so it does nothing.

``````            0

0  0  1  1   2  0

1  1  2  2  2

1       2  2  0

2   2

0
``````

So the only thing you have to check to determine if you should propagate is which update is the most recent.

Also, it is possible that multiple values are changed at once, so it should be able to handle that as well, i.e

``````            0

0  0  0  0   0  1b

1a 0  0  0  0

0       0  0  0

0   1c

0
``````

It can handle this but you've created a non deterministic race. Some final values will be determined not by the data but by processing order. There is no algorithm to fix this. Once you decide that all three updates "changed at once" they all have equal validity.

``````            0

0  0  1a 1a  1b 1b

1a 1a 1? 1b 1b

0       1? 1? 0

1?  1c

0
``````

And this situation pokes a hole in DFS because you can't emulate real propagation, in this situation, that way. Propagation happens breadth first.

So if you want to handle distributed updates you need some way to put them in order and decide which one wins, unless you don't mind letting them race for it.

• +0 – The symbols I was using was more of a visual animation then actual states, but probably should've mentioned that. Thank you for pointing out the race condition, I totally missed that. I have no idea what to do there, hmm... — Jul 02, 2018 at 04:32
• +0 – @LancePollard I suspected something like that but really can't see a way to say something useful using it. So I changed the symbols. — Jul 02, 2018 at 04:34
• +0 – It goes back to the unchanged state because I assumed that, once all the values have been updated, you want to treat it as if it is in a brand new fresh state, so it can receive the next batch of updates. Also, it doesn't need to necessarily propagate the way I showed, if DFS is better, I wasn't too particular about that. — Jul 02, 2018 at 04:36
• +0 – @LancePollard I get that but it hides what's going on. I used symbols that make what happens brutally clear. — Jul 02, 2018 at 04:38
• +0 – Makes sense, I like it. — Jul 02, 2018 at 04:39