How do I resolve asynchronous client actions against an authoritative server state?

Question

I have a multiplayer card game which I am in the process of developing.

The game is relatively simple; players have a certain number of cards which they can activate, sell, or use in various other ways.

The game isn't turn based. Instead, it is asynchronous so that players (A, B, C, and D) all make their choices at the same time. Certain actions will affect the game state. For example, removing a card from the game or adding a card to the game. Players should always be in sync with each other so that, for instance, Player A cannot use a card that Player B has just removed, as it is no longer present.

Obviously there are situations in which Player A may remove a card at nearly the same time that Player B tries to interact with the same card. How would the server handle this sort of situation?

My original thought is that each client could hash their game state and send it with their command to the server, for example:

Player A - #MYHASH# - Command = Pick Up Card Z

Player B - #MYHASH# - Command = Remove Card Z

The server would then action the first command and regenerate the hash. Upon trying to execute the second command it would notice the hash sent by Player B differs from the current hash, so the server would reject the request.

In the above example Player A would notice nothing and the game would continue normally, but Player B would have to be informed that their action failed.

Answer 1

A hash of the state is the right general idea, but the wrong specific implementation; two different states could hash to the same value, and while that might be a rare occurrence (depending on your hash algorithm), it's still a case you want to handle.

Instead, consider a sequence ID. A sequence ID starts at some initial value and is updated by the server after every validated change to the game state. When the server sends an update to all clients, part of that update includes the new state sequence ID. When the client sends a request to change something to the server, it includes the sequence ID that goes along with the state it currently has.

When the server gets a request from the client, if the included client sequence ID is not the same as the current sequence ID, the update is rejected because the client had a stale state; the server should inform the client (along with the new state and sequence ID). Otherwise the server accepts the move, updates its state and sequence ID, and broadcasts the change to all clients.

Obvious this update on the server has be synchronized, but that's true anyway since you're modifying the game state anyhow.

The downside to this approach is that the client cannot dispatch multiple state change requests to the server; after sending one, it has to wait to get confirmation and a sequence ID update. There are several solutions to this, but I think the ideal solution is to simulate the successive moves locally as if the server said "yes" to everything, but keep them queued in memory. As the server confirms each move, send the next queued action until the server state catches up with the client. If at any point you get a response from the server that wasn't a confirmation of that client's own action (that is, an update from another client), discard the remaining queued up actions and resynchronize the game state, displaying an appropriate error message to the user if needed.

This system can be used as the basis for fault-tolerate (that is, crash-tolerant) persistence systems as well -- if you have a storage backend with transactional guarantees, like a database, you can persist update requests and sequence IDs and be able to resume the same sequence of transactions after a crash. It can allow for idempotent operations, also; what I've described is a simplified view of the basis for item transfer systems in the MMOs we build where I work.

Answer 2

Just send in the commands. If B asks for a card that A already took, the server can send a YoureOutOfLuck event in response. That simple.

Your bigger worry is the UI. You need to immediately provide feedback for clicks, but have to wait to do any real action until confirmation. Making a good click effect that is not too long/annoying but gives enough time for typical RYT/acknowledgement is tricky.

Answer 3

You'd want to check out optimistic locking.

For a practical implementation, if you are using HTTP for your communication, check out how HTTP uses ETag and If-Match HTTP header for conflict detection. If you don't use HTTP for your communication or if you use HTTP only as an envelope to your own request, try to base your design like ETag and If-Match.

In your particular situation, what would happen is that the server should attach an entity tag representing the game state to all game state updates that are sent to the client. The client would then have to attach the received tag in its move requests, the server checks that if the tag in the request does not match the current gamestate tag, then the request is refused; if the tag matches the current gamestate hash, the request is processed by the server and an update is pushed to all clients who will then have to update their game state and tag. If the client's request is refused then the refused client will also update its game state and tag, but also inform the user that they cannot do the requested action.

To calculate an entity tag, you can use a hash of the gamestate, a random number, or a sequence number as long as you generate it consistently. The advantage of a hash is that you don't need an extra database field to store the tag as you can easily regenerate it from the current game state. Whichever method you choose shouldn't matter for the client, since the entity tag is opaque for the client.