How to avoid oscillation by async event based systems?

Posted by inf3rno on Programmers See other posts from Programmers or by inf3rno
Published on 2014-05-31T11:49:45Z Indexed on 2014/05/31 15:58 UTC
Read the original article Hit count: 187

Filed under:
|

Imagine a system where there are data sources which need to be kept in sync. A simple example is model - view data binding by MVC. Now I intend to describe these kind of systems with data sources and hubs. Data sources are publishing and subscribing for events and hubs are relaying events to data sources. By handling an event a data source will change it state described in the event. By publishing an event the data source puts its current state to the event, so other data sources can use that information to change their state accordingly.

The only problem with this system, that events can be reflected from the hub or from the other data sources, and that can put the system into an infinite oscillation (by async or infinite loop by sync). For example

A -- data source
B -- data source
H -- hub

A -> H -> A -- reflection from the hub
A -> H -> B -> H -> A -- reflection from another data source

By sync it is relatively easy to solve this issue. You can compare the current state with the event, and if they are equal, you don't change the state and raise the same event again.

By async I could not find a solution yet. The state comparison does not work by async event handling because there is eventual consistency, and new events can be published in an inconsistent state causing the same oscillation. For example:

A(*->x) -> H -> B(y->x)
    -- can go parallel with
B(*->y) -> H -> A(x->y)
    -- so first A changes to x state while B changes to y state
    -- then B changes to x state while A changes to y state
    -- and so on for eternity...

What do you think is there an algorithm to solve this problem? If there is a solution, is it possible to extend it to prevent oscillation caused by multiple hubs, multiple different events, etc... ?

update:

I don't think I can make this work without a lot of effort. I think this problem is just the same as we have by syncing multiple databases in a distributed system. So I think what I really need is constraints if I want to prevent this problem in an automatic way. What constraints do you suggest?

© Programmers or respective owner

Related posts about algorithms

Related posts about concurrency