Agreeing of a thing between two computers.

something

x:
send y change
queue change
receive update change
change

update status

y:
receive x change
queue change
send update change
change

update status

Kuphryn

Do they have to change the data at the same time, because you're using lock-step simulation? If so, you can queue the change for some time in the future (say, now + N steps of simulation). Separately, synchrnize the advancement of simulation so that each of the players have gotten all of the data sent during a given frame until advancement is allowed. Use re-transmission to make sure that advancement happens in the face of drops. (Or, perhaps better, just use TCP in this case).

Do they both have authority over the data? If so, you can let Alice optimistically make the change, send the change to Bob, and if Bob rejects the change, send the rejection back to Alice, who will have to roll back the change (the theory being that rejection will be un-common). Again, you can use a reliable messaging mechanism, such as TCP, to avoid the "what if the packet gets lost" problem, assuming authority is more important than latency.

For lossy protocols (typically over UDP), keeping low latency is MORE IMPORTANT than keeping the simulation 100% in sync. The theory is that, if some packet is lost, a future packet will make up for the deficiency, because state is evolving quickly.

If you need both low latency, and absolute authority, then you need to be on a LAN, where TCP performance can be guaranteed :-)

kuphryn: Will not work if "send update change" (from Y) is not recieved by X, then X will not change it's value but Y will.

hplus0603:

Quote:

Do they have to change the data at the same time

No, not really it's more something like this: "If Alice changes the Data, Bob must also do so (before any other changes to Data is made)".
But I like it to change withian a reasonable amount of time, i.e a few messages sent and recieved (2-3 seconds would probably be ok).

It got nothing to do with lock step and/or simulation steps.

Quote:

Do they both have authority over the data?

Yes the change of Data can come from either Alice or Bob.

Quote:

If so, you can let Alice optimistically make the change, send the change to Bob, and if Bob rejects the change, send the rejection back to Alice, who will have to roll back the change (the theory being that rejection will be un-common). Again, you can use a reliable messaging mechanism, such as TCP, to avoid the "what if the packet gets lost" problem, assuming authority is more important than latency

I'm not really talking about packets getting lost here, I'm more worried about someone pulling the plug :) Or a crash of one of the systems.
Thinking about it, it's more like keeping the Data synced, so if Alice connects to Bob, Bob will know Alice's Data value, without Alice having to resend it.
This might be unsolvable, I'll try to work around it by comparing the checksum of Alice's and Bob's Data during the connecction phase and resend if necessary, dunno if it'll work out though.

The minute I read this post, I remembered (vaguely) something from school called a 'two level transaction', or something like that. I looked it up, and it's called the two phase commit.



So, see if it does the trick for you:

http://en.wikipedia.org/wiki/Two-phase_commit


Or, if you need the protocol to be non-blocking, you can use a three phase commit:

http://en.wikipedia.org/wiki/Three-phase-commit_protocol

At a first glance it seems like the three phase commit might work.
I knew about the two phase commit and that it wouldn't work.
Never heard about the three phase commit though, need to get my head around it before I can tell you if it worked for my application.

Cheers!

If both Alice and Bob want to make changes to an object, and will not allow the others to make changes until the first change is committed, then you need a fully-fledged transaction model.

If you're peer-to-peer, then you could pass a synchronization token back and forth. Easiest: decide that Alice can make changes to the world on even turns, and Bob on odd turns. Alternative: keep a synchronization token for each object. When A wants to change object Y, it requests the token (unless it already has it). B passes along the token, along with the changes to state it's made since it got the token (to make sure A is in sync).

Note that, if A has the token for object X, and then goes down, B cannot actually get the token, and any request on B to change the state of X will have to stall until A comes back, because A might have committed changes to X that B doesn't yet know about. (That's a problem that a separate transaction monitor can possibly help with.)

If you can go client-server, then you can introduce a transaction monitor role, and use two-phase commit.

Note that you might as well use TCP for this protocol -- if you use UDP (where you have to worry about packet loss), you will end up re-implementing the TCP semantics anyway.

Now, if state has to persist across sessions (say, someone trips on a wire), then you can store a generation count which is updated every time someone gets the token. Each node has to store the last checkpointed generation count, along with some backlog of generations (at least one old generation). When the system starts up again, the nodes ask each other about the latest generation count stored among the nodes, and settle the differences.

Distributed state authority is really hard. If you need low latency and high performance, you're probably better off re-designing; either to relax the consistency requirements, or to remove the requirement to have authority in more than one place.

Firstly, use TCP, then the only way the message can not be received is if the connection is lost. Coping with one potential, detectable loss mechanism is easier than coping with UDP's hard-to-detect packet loss.

Having said that you need a transaction model such that if a connection is lost you back off to the previously agreed transaction. Something like ...

A: begin transaction id 41
B: ack 41
A: set data 300
B: ack 300
- Now both A and B know that data is supposed to be 300, but it's not committed. A knows that B knows, so A asks B to commit
A: end transaction 41
- At this point B commits and updates its transactions to 41 as well, but also saves the previous version
B: ack 41
- If A doesn't receive this, it doesn't commit at its end. If it does, it commits the change and clocks its 'completed transactions' to 41

Now, if the connection is dropped any time before B's 'ack 300' is received, no harm done. The only bad place is if it drops before 'ack 41' at the end, in which case A cannot tell whether B has updated its version or not. It doesn't commit the change in that case so it knows B is not behind it.

This will be true whatever sort of confirmation you use, so you have to store the state before the last transaction as well (only in the recipient, B, in this model) so when the connection is remade the two computers can ask each other what their transaction count is. It can only be different by one, and if there is a discrepancy the higher (B) must tell A to rerun that transaction.