COP State Update Algorithms

This page describes the COP update algorithm which allows a control server to update the state in a VIRGO instance.

A control server and the VIRGO instances tethered to it share state. This states describes among other things which feeds exist and what the feed settings are. Delta updates are the preferred mechanism to update a VIRGO instance to new state. They are very efficient and free from data races. Nevertheless the COP protocol supports full state updates because they are key to enabling reliable resynchronization in the event that VIRGO and its control server got out of sync.

Delta updates are reliable because the design of the delta update mechanism is based on the following key principles:

The key principle which informs every other aspect of the design is that the control server and only the control server defines at all times what the truth of the shared data is. The state stored in VIRGO is in principle untrusted. Only after the control server has received a status message from VIRGO and the control server has validated that the mod-date that VIRGO sent is the expected mod-date, is the VIRGO state considered trustworthy and correct until the next status message is received.

The Nature of a Mod-Date

Mod-dates are simple 64 bit integers which represent the current state of the shared VIRGA-VIRGO state. Every time the state changes for some reason the mod-date has to change too. Mod-dates have to be unique in the sense that if you have two states A and B which differ in some form then state A and state B have to identified by different mod-dates.

The meaning of mod-dates is defined by the control server and the control server decides how mod-dates are generated and changed over time. VIRGO does not interpret the bits of a mod-date. It only cares about the fact that two mod-dates which are associated with different sets of data have to be different bit patterns.

Note that although mod-dates are called “mod-dates”, they technically do not have to be dates. A mod-date may be any random but unique number. The only thing that is important is that they are unique.

That said a simple way to generate unique mod-dates is by using the current time when the data is changed. Another simple way is to atomically increment an integer every time a change is applied to the data stored in the control server database.

The Update Timeline

There is a timeline associated with the shared state. This timeline starts at an epoch point and then continues to move along the time axis as the state continues to evolve. Every time the state changes from a previous version to a new version the associated mod-date is changed too.

There are really three mod-dates associated with the shared state:

Both the virga-mod-date and the expected-mod-date are persistently stored in the control server’s database while the virgo-mod-date is stored in VIRGO’s local database.

The following sections explain how the update algorithm works.

Timeline Epoch

The very first time a control server communicates with a VIRGO instance, the control server does not know which state the VIRGO instance stores and neither does it know what the virgo-mod-date is. Consequently the control server has to do a full state update to adopt the VIRGO instance and to sync it up to its own state.

The control server does this by sending a delta update with the “relative-to” property set to “initial”. This tells VIRGO that it should remove all stored data and revert back all its stored settings to its factory defaults. It also tells VIRGO that it should set its virgo-mod-date to the mod-date of the initial message.

From that moment on the VIRGO instance can be considered linked/tethered to the control server and it accurately reflects the current state of the control server.

Updates

The following graphic shows how the timeline of the shared data evolves as updates are applied to the data.

“Virga” here refers to the control server and “User” refers to some kind of user interface which allows the user to view and update the data stored in the control server. Typically VIRGA and VIRGO will run on different machines and are linked through a reliable or unreliable network connection.

The VIRGO state and virgo-mod-date are unknown to VIRGA in the very beginning. This is why in response to the very first status message that VIRGA receives from VIRGO it sends an “initial update” to VIRGO. This initial update is an update with “relative-to”: “initial” and whatever else properties VIRGA wants to push out to VIRGO to sync it up with its own state. From that moment on VIRGO status messages will contain a mod-date which is equal to the expected-mod-date that VIRGA has stored.

VIRGA maintains two mod-dates in its local database: an expected-mod-date and a virga-mod-date. The virga-mod-date is updated by VIRGA every time the user changes the data. The expected-mod-date on the other side is only then updated by VIRGA when it pushes its state to VIRGO. At this time the expected-mod-date is set to the current state of the virga-mod-date. The two mod-dates are used by VIRGA to detect out-of-sync conditions (see next section). Note that the inequality virga-mod-date >= expected-mod-date >= virgo-mod-date is universally true in this scheme.

Every time the user changes the data in the VIRGA database, VIRGA increments its virga-mod-date. This new mod-date together with the new data is pushed to VIRGO in response to the next status message that it receives from VIRGO. VIRGO then applies the new data to its current state and it sets its virgo-mod-date equal to the mod-date that was passed along with the update message.

Detecting Out-Of-Sync Situations

It is the responsibility of the control server to detect out-of-sync situations. It can do this easily by comparing its expected-mod-date with the mod-date provided by VIRGO in a status message. Assuming that the mod-date that VIRGO sends in a status message is called “status-mod-date” then VIRGA and VIRGO are out-of-sync iff expected-mod-date != status-mod-date.

Resyncing the Shared State

The control server should initiate a resync of the shared state as soon as it has detected an out-of-sync situation. The following graphic shows an out-of-sync situation and how the control server is expected to detect and correct it:

Note that VIRGA sends an update message to VIRGO with a mod-date of 8 but VIRGO for some reason failed to apply this update. Consequently the virgo-mod-date (the mod-date stored inside of VIRGO) remains at 7 but the control server has advanced its expected-mod-date to 8 because the virga-mod-date was 8 at the time when the control server pushed the update to VIRGO (remember that the expected-mod-date is set to be equal to the virga-mod-date at the time when an update is pushed to VIRGO).

The next time VIRGO sends a status message to VIRGA, VIRGA’s expected-mod-date == status-mod-date (the mod-date from the VIRGO status message) fails. Because of this VIRGA realizes that VIRGO is no longer in sync and that the current state of VIRGO can no longer be trusted. VIRGA now generates a full update with the mod-date 8 and pushes this to VIRGO. This forces VIRGO to replace its current state with the VIRGA provided state.

This full update can be achieved in one of two different ways:

Why Resyncing is Important

The ability to reliable detect out-of-sync conditions and to efficiently and reliably correct them is a major capability of the COP protocol. But you may be wondering how it is possible for the state of the control server and VIRGO to get out-of-sync. Here are some possible reasons why:

No matter what the reason for an out-of-sync situation is the control server is always able to resync the VIRGO instance if it implements the COP update algorithm correctly.

See Also