Skip to content

New scheduling algorithm

Trying to come up with a scheduling algorithm that solves the problem of "delayed" data as described in #75 (closed) and #76 (closed).

Solution idea

Prerequisites:

  • Components that don't want to use "delayed" should be able to make a prediction about their next pull time (or next time, or the next step size)

In each iteration, do the following:

  1. Select the component most back in time as current component
  2. Determine the current component's next time
  3. Check all components it directly depends on whether they are at or beyond that next time already
  4. If there is any such components, make it the current component and go to step 2
  5. If there are no such components, update the current component

If there are circular links, we will get to some component twice with the above algorithm, and know that it can't work.

To break circular dependencies, we could use an adapter for exactly that purpose, that also does the extrapolation.

Components that are fine with using data as is would be provided with the current scheduling algorithm could just use return their current time as next time, and would (i think) also break circular dependencies.

Example: A depends on B and C: B >> A, C >> A

 A -o-----o     x
 B --o--o--o
 C o---o---o

Select A; depends on B, which is not as x yet --> update B (has no dependencies, repeated 2x)

 A -o-----o     x
 B --o--o--o--o--o
 C o---o---o

Select A; depends on C, which is not as x yet --> update C (has no dependencies, repeated 2x)

 A -o-----o     x
 B --o--o--o--o--o
 C o---o---o---o---o

Select A; all depnendencies are at x -> Update A

 A -o-----o-----o
 B --o--o--o--o--o
 C o---o---o---o---o

Possible problems

We can't be sure anymore to be between the last two updates of an upstream component

Example: A depmends on B and C, and B depends on C

A o---o---o   x
B --o--------o
C -o--o--o--o

Here, A would be on turn and forces B to update, which forces C to update
Update C:

A o---o---o   x
B --o--------o        x
C -o--o--o--o--o--o--o--o

Update B:

A o---o---o   x
B --o--------o--------o
C -o--o--o--o--o--o--o--o

Here, all the data of C would need to be stored

A possible solution could be that outputs know all their target end-points (easy with the ping that is already in place). They could then manage data storage/clearing on the earlieast pull data of all end points.

Edited by Martin Lange