Copyright 2020-2021 Ian Jackson and contributors to Otter SPDX-License-Identifier: AGPL-3.0-or-later There is NO WARRANTY. CONCURRENT UPDATE PROTOCOL AND ANALYSIS ======================================= (Assumption: our network techniques deliver messages in order in both directions between a server and a client; failure of the communication stream is allowed to break things - we treat it as fatal.) We run the following algorithm / data model separately for each piece. Model ----- There is: * actual committed history, a list of updates * the history seen so far by the client this can only advance, which is a prefix of the above * possibly branch(es) of history made by the client; this can rewind and be discarded There is a digraph of updates. Each update specifies the complete state of the piece. The server maintains an authoritative history; the client only maintains the state of the piece. Updates may be from this client ("`Client` updates") or from another client or made by the server itself. We look at the protocol from a single client's point of view, and call all the other updates "`Server` updates". Each update has a single direct ancestor, but this is not recorded in the message nor by the client. Updates may be some combination of: * `Recorded` - stored by server. * `Downbound` - on way from server to client. * `Discarded` - received by server and thrown away. * `Upbound` - on way from client to server. * `Displayed` - seen by client, is most recent state there * `Superseded` - seen by client, is no longer most recent state. Server assigns generation number (strictly increasing but maybe with gaps) to each `Recorded` update. Each `Upbound` update is tagged with the generation of the most recent Processed update. (Actually the most recent Processed generation stored by the client is global across all pieces, and the server's generations are likewise generated globally although recorded separately for each piece. So the update contain s a generation >= the most recently Processed update for that piece, and < any subseuent Processed upate for that piece. The server only compares the incoming update generation for >= with a recorded value, so this makes no difference.) Desirable properties and invariants ----------------------------------- Legal combinations are: * `Server` + `Recorded` + `Downbound` * `Server` + `Recorded` + `Displayed` * `Server` + `Recorded` + `Superseded` * `Client` + (`Displayed` / `Superseded`) + `Upbound` * `Client` + (`Displayed` / `Superseded`) + `Recorded` * `Client` + (`Displayed` / `Superseded`) + `Discarded` _linear_: The `Recorded` updates form a linear sequence (so it is only ever appended to). _forwards_: Each update has at most one `Server` descendant, and at most one `Client` descendant. _display_: Exactly one update is `Displayed` at any one time. It has no `Client` child and no `Superseded` descendants. Each update is only `Displayed` at most once, and can only become `Superseded` after having been `Displayed`. _discard_: For every `Discarded` update K there is a `Recorded` `Server` update S which not an ancestor of K; and with S's generation > K's tag. _record_: Sequence of `Recorded` updates is as follows: * `Recorded` `Superseded` (zero or more) * `Recorded` `Displayed` (zero or one) * `Recorded` `Downbound` (zero or more) Update generation operations ---------------------------- ### I. Server update ### Server may invent and transmit an update at any time. Its ancestor is the most recent `Recorded` update. It is `Recorded`+`Downbound`. No other updates change their state. Properties and invariants: _linear_, _forwards_, _record_ are obvious. _display_ is not affected. ### II. Client update ### Client may invent and transmit an update at any time; it must have the `Displayed` update as its parent. That update becomes `Superseded`. The new update is `Displayed`+`Upbound`. _linear_ and _record_ are not affected. _forwards_ is honoured because of _display_. _display_ is preserved. Server message reception ------------------------ Suppose the server receives a message, Q. It was `Client` `Upbound`. Let T be the most recent `Recorded` message. The server finds the most recent `Server` `Recorded` message, U. ### I. Q's generation is >= U's generation. ### The server records Q with T as parent. Q becomes `Client` `Recorded`; it is `Displayed` or `Superseded` as before. _linear_: We need to show that T really is Q's parent. If Q's generation >= U's generation, the ancestry path have been received by the server. So they must be `Recorded` or `Discarded`. Suppose one, K, was `Discarded`. Then by _discard_ there is some `Recorded` `Server` update S which is not an ancestor of Q. S's generation must be > Q's tag, since Q's tag is >= all of its `Recorded` ancestors. So S's generation > U's. But this means that S is a `Server` update more recent than U. _|_ So everything in is `Recorded`. Only Q is not `Recorded`. Therefore Q's parent is indeed the most recent `Recorded` update, T. _forwards_: We aren't making new messages. _display_: We aren't changing any of this. _discard_: we aren't discarding anything. _record_: Let S be the most recent `Recorded` `Downbound` update S. This must be U. But Q's generation >= U's generation so U can no longer be `Downbound`. So there are no `Downbound` updates. Maybe Q is `Displayed`; in any case all older `Recorded` updates are `Superseded`. ### II. Q's generation is < U's generation ### The server discards Q. It becomes `Discarded`. _linear_, _forwards_, _display_, _record_: No change. _discard_: Q becomes K. Use U as S. U is `Recorded`. If Q had U as an ancestor, U's generation would have been visible to the client when it generated Q, so Q's tag would have been >= U's generation. S's generation is U's generation and is >= Q's by case assumption. Client message reception ------------------------ Suppose the client receives a message Q. It displays it. (The currently `Displayed` update becomes `Superseded`. Q becomes `Displayed`.) _linear_, _forwards_, discard_: No change. _display_: Q is a `Server` update because it was `Downbound`. We have just received it so it cannot yet have any `Client` descendant. It might have `Server` descendants, but those are also `Recorded` `Downbound`, by _record_. _record_: By order of delivery, Q is the most recent `Recorded` `Downbound`. Liveness property ----------------- "When things ahve settled, all is consistent." If there are no `Upbound` or `Downbound` updates, the most recent `Recorded` update R is `Displayed`. Suppose some update D is displayed instead. D can't be `Recorded`. If it were, R would have to be `Downbound`, by _record_. So D can't be `Server`. Suppose D is `Client`. It must be `Recorded`, `Upbound` or `Discarded`. Only `Discarded` is left. If D is `Discarded`, by _discard_, there is some `Recorded` `Server` S which is not an ancestor of D, with S's generation > D's. S must be `Displayed` or `Superseded`, since there are no `Downbound` updates. If S were `Displayed` it would be equal to D, hence D would be an ancestor of S. So S must be `Superseded`. If S is `Recorded` `Superseded`, at some point it was `Displayed`. D is now `Displayed`. So D was `Displayed` more recently than S. D is `Client` so when it was `Displayed` it became `Upbound`, tagged with a generation of at least S's; i.e. D's generation >= S's. _|_ SERVER ACKS =========== Actually, the client wants to know when conflicts occur, so that it can report to the user, and interrupt drag operations etc. To this end: Update messages from the client to the server also contain a client sequence number (monotonically but not strictly increasing). When the client sends an update, it makes a note of the sequence number. This is the "outstanding Client updates sequence number note", or the **oustanding note**. When the server processes a message from the client and Records it, it puts the client sequence number in the update stream (as a non-update message). (This is skipped if it's the same as the last client sequence number for that client.) If the echoed sequence number is equal to the client's _oustanding note_, the client knows the server is up to date, and deletes the note. If the client sees a Server update message, and the client has a _note_, it knows that there was a conflict. LEVEL (Z ORDER) =============== Each piece has a Z level (an arbitrary-precision value in <0,1>), set by the client which manipulates the piece, according to the protocol above. Each piece *also* has a Z level generation. This is set by the server. The server guarantees to set it to the server generation, and guarantees to do so as the result of any client Z level update. So the client which sends a Z level update can assume that a server update to the generation will turn up, and with a higher value. The Z generation is used to disambiguate the Z order for pieces with identical Z level. Higher values are closer to the user (ie, occlude lower values). ERRORS ====== Most of the time, the client will be able to predict what the server's response to an update will be. So usually, a `Client` `Upbound` update will become `Recorded`, unless there was a conflict. However, sometimes this is not the case: a piece can have behaviours which are too complicated to model in the client. In such cases, the server will be processing a `Client` `Upbound` update, and find that it cannot be applied and made `Recorded`. (Call that an **inapplicable** update.) When the server receives an update it deems _inapplicable_, it will generate a `Server` update and process that before the incoming `Client` update. The `Server` update will inform the client of the problem, and, by its existence cause the `Client` _inapplicable_ update to become `Discarded`. When the client receives the `Server` update, it can describe the problem to its user, and also note that the `Client` update has become `Superseded`. Additionally, of course, the client might have bugs (or be malicious). So there can also be `Client` updates which the client ought to know are **bogus**. This includes syntactically malformed updates, but it could also include updates with semantic errors. _Bogus_ updates might not fit into the update synchronisation protocool. Since they arrive by HTTP, the server can reject them with an HTTP error code. A non-malicious client can deal with that by reporting the problem immediately to its user (although synchronisation will be lost). In theory the server might be able to predict precisely what the client can know, and precisely distinguish between `Client` updates which are unprocessable because of something only known by the server, and ones which are unprocessable because of misbehaviour (eg, bugs) at the client. However, getting this right is very fiddly and complex. In the absence of buggy or malicious clients, there will be no _bogus_ updates. And since even _inapplicable_ updates are rejected by the server, there is no harm to anyone else of treating an update as _inapplicable_ rather than _bogus_. So we err on the side of treating client mistakes as due to synchronisation and incomplete modelling: ie, we only treat a client update as _bogus_ if it is patently obviously wrong (for example, it is syntactically invalid). Fatal errors which the client could not have predicted, but which are not recoverable, can also be treated as bogus. REGRAB ====== Additionally, there is one special kind of operation, which allows a limited degree of desynchronisation between client and server. We want that player who has just released a piece, may immediately regrasp it, even if concurrently there is a `Server` update in flight which is the result of the release. This is because drawing a card from a pickup deck does not reveal the card until the player releases it, but the player will often want to immediately play the card. The server will only honour a regrab update if it comes from the same client as the last client to ungrab the piece. Formally this introduces a new flag on `Client` updates: whether they are, **`Loose`**. The client which generates an update decides whether it is `Loose`. When the server receives a `Loose` update which seems to be out of date it will decide (using its own algorithms) whether it should still be processed, and if so, what that means. If it likes the update, it will generate a `Server` update implementing its decision. The client's _outstanding note_ records whether the outstanding branch is precisely a `Loose` update. If so, `Server` updates do not clear the note until a `Server` message is received acknowledging that client sequence. After `Display`ing a server update, when there is an outstanding `Loose` `Client` update, the client may, but is not required to, "replay" the effect of the `Loose` update, to show its user what the predicted effect will be. Likewise it may discard the note of the outstanding `Loose` update if it thinks it will inevitably generate a conflict.