Performance Parameter Change Race Conditions

Problem Statement

Performances are sets of users controlling a replicated project. Performances allow multiple users to share the control of a project and to hear very simpler high-quality sound, which is created locally for each user. Local parameter changes are transmitted to all other instances of the project within the performance.

Local parameter changes take effect immediately in the local project. Changes are relayed through the server to all other project instances within the performance and take effect as soon as they are received.

If two users change the same parameter, a race condition is created: Suppose User1 changes a value to V1 and then User2 changes it to V2. User1 will see the change to V1 immediately, and after network delay, will see it change to V2. User2 can either see the change to V1 just before the local change to V2, with a final value of V2. Or, User2 can change to V2 just before V1 arrives, with a final value of V1. Thus, there is a "race" that determines the final value.

This is unacceptable because the sound generated for User1 and User2 could be very different. Our goal is to limit sound differences to momentary discrepancies due to network delay. There can still be longer-lasting differences due to internal state such as order of random number generators, oscillator phase, etc., but we will not try to eliminate these differences.

Solution

Standard approaches to race conditions including mutual exclusion, transactions with roll-back, and timestamps. Here, we introduce a new approach that uses the server to impose a total ordering on updates.

Assumption: The server receives one update message for every local update. Every update message is transmitted to every user in the performance, including the originator of the update. Every update message contains at least:

• a parameter identifier (which we ignore in this description -- it should be clear that we treat every parameter in the same way),
• a value,
• a sequence number (an integer that is incremented every time there is a local change to the value)
• a unique identifier for the sender (this could be an IP address or a server-assigned index number or even a random number with enough bits to ensure it is unique, for example).

Every parameter will be represented locally as a pair of current value, sequence number, and confirmation boolean: (V, N, C). When a local update is made, the confirmation is cleared, resulting in the state (Vnew, N+1, false), where Vnew is the new value, N+1 is the new sequence number, and the confirmation is false. An update message (Vnew, N+1, localID) is sent to the server containing the sender's identifier. When an update message is received from the server:

• if the message is (V, N+1, localID), this is an echo of the message we sent. Change the local value to (V, N+1, true).
• if the message is (V, i, localID), where i < N+1, then this is an echo from an earlier update (there might be multiple updates in flight); it is stale, so ignore it, and keep the local state (Vnew, N+1, false).
• if the message is (Vs, i, s), where s is not the client's localID, then someone else sent this update. If the state is (Vnew, N+1, true), then the update was received by the server after our last update, so give priority to s, and change the local state to (Vs, N+1, true). (Note that we do not record the sequence number i from s: We need to remember our last sequence number N+1 so that our next local update can be numbered N+2.

Behavior

This approach seems to have reasonable behavior.

Any local change will take place immediately. Local changes will be held until a round-trip completes with the server, except that subsequent local changes will take place immediately. Any changes to a parameter arriving at the server after the last local update will take effect as soon as they are received by the browser.

One consequence of this design is that a user can "lock out" any updates by making continuous local updates. E.g. if you drag a slider and generate an update every 100ms, but the round trip to the server is 200ms, then you will always have an update "in flight," your confirmation state will always be false, and all updates from other users will be ignored. It would be possible to give visual feedback, e.g. make the visual control flash red, when another update is received and discarded. This could alert a user who is dragging a slider that another user is also controlling that parameter. But this seems unnecessary and the point is collaborative performance, not fighting over parameter values.