There are several types of negotiations used to synchronised the parties of a network connection. - Continue when we know the other is ready ("Ready") This is used when both parties need to sending information to the other side, but what each party is doing does not interfere with what the other party is doing. - Agree on changes ("Update") This is used when the parties have changes to make to common data. - Mutual agreement on an action ("Confirm") This is used to end a state where both parties are modifying common data. Both parties have to agree with the data for either party to continue. - Reset a connection. This is used to abort a game in progress and return to the fleet setup menu. ============================================================================ "Ready" negotiation. Sometimes the parties need to notify eachother of their local state, and then go on when both are ready. For this purpose both parties signify that they are ready by sending the READY message. When a party is ready and has received notice that the other party is ready, it can go on. States: 0. notReady - send nor received READY !localReady && !remoteReady 1. localReady - sent READY, not yet received READY localReady && !remoteReady 2. remoteReady - received READY, not yet sent READY !localReady && remoteReady 3. ready - sent and received READY Messages: - READY - "I have nothing further to send at this point" From state 0 (notReady): local decision -> Send READY, goto 1 received READY -> goto 2 From state 1 (localReady): received READY -> goto 3 From state 2 (remoteReady): local decision -> Send READY goto 3 ============================================================================ "Update" negotiation. During configuration, both sides may change the same properties. So that the two sides don't have to take turns, the changes are made locally, and then the changes are synchronised. To this end, each side has a state containing two copies of each property: 1. The value of the property as it is locally 2. The last value which it sent to the other side (until it is no longer relevant for the protocol) The basic idea of the Update protocol is: - both sides each send and receive one packet before being allowed to send another one (we'll call this a "turn" here) - when a packet has been sent and one has been received in a turn, and the sent and received values are the same, then that value is the agreed upon value. If the sent and received values differ, then a tie breaker determines which one prevails. - when the first local change of a turn is made, the change is sent to the other side - when a local change has been made while a packet has already been sent this turn, the change will be made locally, but communicating the change will be postponed - when a turn ends while a change has been postponed, and this change isn't negated by a remote change, then the change will be sent - when a remote change arrives, and a packet has not been sent this turn, the local state is updated with the change, and the same packet is sent to the other side to confirm the change The tie breaker is required to always let one side win, and the other side lose, given the same property. Any function satisfying this requirement is usable, but the currently used one will return true for the side which 'owns' the property, and false on the other side. Another tie breaker could be one which always lets the same side win, regardless of the property. The protocol: From state 1, {own=x0, sent=--}: 1a Local change x1 -> send(x1); state=2:{own=x1,sent=x1} 1b Received UPDATE(x1) -> send(x1); state=1:{own=x1,sent=--} From state 2, {own=x0, sent=x0}: 2a Local change x1 -> state=3:{own=x1,sent=x0} 2b Received UPDATE(x0) -> state=1:{own=x0,sent=--} 2c+ Received UPDATE(x1) -> state=1:{own=x0,sent=--} if winTieBreak 2c- Received UPDATE(x1) -> state=1:{own=x1,sent=--} if !winTieBreak From state 3, {own=x1, sent=x0}: 3a Local change x0 -> state=2:{own=x0,sent=x0} 3b Local change !x0 -> state=3:{own=xN,sent=x0} 3c Received UPDATE(x0) -> send(x1); state=2:{own=x1,sent=x1} 3d+ Received UPDATE(!x0) -> send(x1); state=2:{own=x1,sent=x1} if winTieBreak 3d- Received UPDATE(!x0) -> state=1:{own=x?,sent=--} if !winTieBreak Explanation: We keep track of the local value ('own'), and whether or not we sent a packet in this turn ('sent' != '--'), and if we did, the last packet which we sent ('sent'). When we proceed to the next turn, 'sent' is set to '--'. State 1: We have not yet sent a packet this turn (which implies that we haven't made a local change this turn). 1a. A local change is made. We update our local value, and send this to the remote side. 1b. A remote change arrives. We don't have any local change ourselves, so we accept the remote change, and sent it back to confirm. With both a packet sent and one received, the turn ends, and 'sent' is set back to '--'. State 2: We have sent a packet this turn (after making a local change), and have not changed our local value since (or we have changed it and changed it back). 2a. A local change is made. We update our local value, but we have already sent a packet this turn, so we can't report it until the next turn. 2b. A remote change arrives, and it is equal to both our local value and the value which we sent to the other side this turn. This remote notification may be a confirmation of our update, or a coincidental identical remote change. Either way, the packet acts as a confirmation, and we do not need to change anything. With both a packet sent and received, the turn ends and so 'sent' is set back to '--'. 2c. A remote change arrives, and it is not equal to our local value (which is the same as the value which we sent). The tie breaker decides which value prevails. The same value will prevail on the remote side, so there is no need to send any confirmation packets. The turn ends, and 'sent' is set back to '--'. State 3: We have sent a packet this turn, and have made a local change since. 3a. A local change is made back to the value which we sent. No action is required. 3b. A local change is made. We update our local value, but we have already sent a packet this turn, so we can't report it until the next turn. 3c. A remote change arrives, and it is equal to the value which we sent (which isn't equal to the current local value). The sent/received value is the accepted value and the turn ends. But we have changed our value since already, so as the next turn starts, we immediately send an update. 3d. A remote change arrives, and it is not equal to the value which we sent this turn. + We win the tie break, so the value which we sent prevails. But we have changed our value since already, so as the next turn starts, we immediately send an update. - We lose the tie break, so the value which the remote value sent prevails. We accept the value and the turn ends. (An alternative would be to consider the local change(s) which we made after our change was sent as made in the following turn, in which case we would send our current local value in the next turn. The advantage would be that 3d- would become equal to 3d+, so these could be joined (with 3c too), which saves a few if-statements in the code, but this requires another packet to be sent and replied to in what currently is 3d-.) Proof outline that this works: - The states can never get out of sync: After both a packet has been sent and received, both sides (temporarilly) have accepted the same value - There can be no indefinite loop without ongoing local changes. Once there are no more local changes: from state 3 we always go to state 2 or 1, from state 2 we always go to state 1 from state 1 we can only go back to state 1, and only when a packet has been received. So eventually, both sides are in states 1. With both sides in state 1, no packets have been sent in the current turn, so no more packets are there to be received. - Both sides can make changes, as long as the side which wins the tie breaks stops making changes now and then: Without making local changes, a side will go to state 1 eventually. If a side makes a local change, and this is received by the other side while it is in state 1, then that other side will accept the change. The Confirm negatiation is used to finish the Update negotiation. This works because local changes triggered by the reception of remote changes are treated as local modifications for the purpose of the Confirm negotiation. And this can be done because whenever the Confirm negotiation is in a state where remote changes may be expected, local modifications are still allowed (possily after sending a CANCEL packet). ============================================================================ "Confirm" negotiation. Some actions (like agreeing on a configuration) require confirmation from both parties. This section documents the handshaking protocol involved. Each player must manually confirm the action. After a player has confirmed an action, he may cancel it as long as he hasn't received a confirmation from the other party. All messages arrive in the order sent. States: 0. waiting !handshake.canceling && !handshake.localOk && !handshake.remoteOk 1. localOk (cancelable) - sent CONFIRM1 (since last CANCEL) !handshake.canceling && handshake.localOk && !handshake.remoteOk 2. remoteOk (cancelable) - received CONFIRM1 !handshake.canceling && !handshake.localOk && handshake.remoteOk 3. committed - sent CONFIRM1 (since last CANCEL, received CONFIRM1, sent CONFIRM2 (since last CANCEL) !handshake.canceling && handshake.localOk && handshake.remoteOk 4. cancelWaiting - sent CANCEL handshake.canceling && !handshake.localOk && !handshake.remoteOk 5. cancelLocalOk - sent CANCEL and ready to send CONFIRM1, but received no CANCELACK handshake.canceling && handshake.localOk && !handshake.remoteOk 6. cancelRemoteOk - sent CANCEL and received CONFIRM1, but received no CANCELACK handshake.canceling && !handshake.localOk && handshake.remoteOk 7. cancelCommitted - sent CANCEL and ready to send CONFIRM2, received CONFIRM1, but received no CANCELACK handshake.canceling && handshake.localOk && handshake.remoteOk 8. done - sent and received CONFIRM1 and CONFIRM2 (since last CANCEL) Handshake messages: - CONFIRM1 - "the current local configuration is OK for me" - CONFIRM2 - "acknowledging your CONFIRM1; my own configuration is unchanged since I sent CONFIRM1 (after the last CANCEL)" - CANCEL - "forget about my earlier CONFIRM1" - CANCELACK - "received your CANCEL" MESSAGE(x) indicates any other message. From state 0: (waiting) local confirmation -> Send CONFIRM1, goto 1 local changes -> Send MESSAGE(changes) (goto 0) received CONFIRM1 -> goto 2 received MESSAGE(changes) -> Process(changes) (goto 0) From state 1: (localOk) local cancel -> Send CANCEL, goto 4 received CONFIRM1 -> Send CONFIRM2, goto 3 received CONFIRM2 -> Send CONFIRM2, goto 8 received MESSAGE(changes) -> Send CANCEL, Process(changes), goto 4 From state 2: (remoteOk) local confirmation -> Send CONFIRM2, goto 3 local changes -> Send MESSAGE(changes), (goto 2) received CANCEL -> Send CANCELACK, goto 0 From state 3: (committed) received CONFIRM2 -> goto 8 received CANCEL -> Send CANCELACK, goto 1 From state 4: (cancelWaiting) local changes -> Send MESSAGE(changes), (goto 4) local confirmation -> goto 5 received CONFIRM1 -> goto 6 received CONFIRM2 -> goto 6 received CANCELACK -> goto 0 received MESSAGE(changes) -> Process(changes), (goto 4) From state 5: (cancelLocalOk) local cancel -> goto 4 received CONFIRM1 -> goto 7 received CONFIRM2 -> goto 7 received CANCELACK -> SEND CONFIRM1 goto 1 received MESSAGE(changes) -> Process(changes), goto 4 From state 6: (cancelRemoteOk) local confirmation -> goto 7 local changes -> Send MESSAGE(changes), (goto 6) received CONFIRM2 -> (goto 6) received CANCEL -> Send CANCELACK, goto 4 received CANCELACK -> goto 2 From state 7: (cancelCommitted) received CONFIRM2 -> (goto 7) received CANCEL -> Send CANCELACK, goto 5 received CANCELACK -> Send CONFIRM2, goto 3 On receiving local confirmation, sending CONFIRM2 is a shortcut for sending CONFIRM1 followed by CONFIRM2. Receiving CONFIRM2 from localOk and cancelLocalOk is accepted just for this shortcut. To prove there are no race conditions, I examine all the combinations of states and messages that are underway. Whenever the order of actions isn't fixed, the result should be the same (eg. recv(CONFIRM1) followed by send(CANCEL) should leave the party in the same state as when the send(CANCEL) preceded the recv(CONFIRM1)). I also check whether it is possible for packets to arrive that aren't expected. ============================================================================ "Reset" negotiation. See src/sc2code/netplay/proto/reset.c ============================================================================ Battle ending negotiation. This negotation consists of: 1. a 'Ready' negotiation, before stopping sending frame data 2. communication of each sides current battle frame count 3. the side running behind processes more frames to catch up States: 0. Playing 1. localReady 2. remoteReady 3. countSent 4. catchingUp 5. awaitingCatchup // Unfinished... partially described in readyForBattleEndPlayer()