Your assumptions are a little off
Publish the updated model M_c to all subscribers. Drawback: if the
model is big in contrast to the change it results in much more data to
be communicated.
What you're describing here is essentially the pub-sub (ie publishers/subscribers) model. Even at scale, it's not very expensive to do because the data being returned is largely the same. Because it's essentially a one-way communication, the response will be essentially the same for all users. Fire-and-forget and create cache points in between if you need to scale larger.
Publish change C to all subscribes. The subscribers will then update
their local model in the same way as the server does. Drawback: The
client needs to know the business logic to update the model in the
same way as the server. It must be assured that the subscribed model
stays equal to the central model.
Now we have a problem. Every client maintains it's own state independent of the server. That means, every response needs to be specifically tailored to the request that's received. Ideally, you'll want to minimize the amount of state that's shared between the clients and the servers.
In games, they do this by only passing along the most basic state information. Even then it's usually done over a UDP connection so that packets that get dropped aren't re-requested. That's why, when games lag they'll usually continue to work but in strange and un-predictable ways. To the game, the simulation is still going on even if everybody else is frozen in time. In a lot of cases it'll even lag the player locally because their own actions need to be received and verified on the server before the action is taken locally.
Ever wonder why most fast paced games can't scale to hundreds/thousands of players. Here's your reason.
Calculate the delta (or patch) of the change (M_c - M = D_c) and
transfer the delta. Drawback: This requires that calculating and
applying the delta (M + D_c = M_c) is an cheap/easy operation.
Works good in theory but synchronization is a tricky business. For example, lets say 15 users are editing a document collaboratively. Edits are organized as transactions much like a database and updates are applied chronologically.
Edits can just be synchronized using time right? Wrong, because there's no guarantee that everybody's clock is in perfect sync. So the only option is to employ a central server to handle transaction management. It's somewhat optimal but when you throw in a hundred hosts that all require two-way communication with the central server, things may grind to a halt.
Hybrid-Models
There are a few cases of hybrid communications models that can push the limits by limiting or shifting accessibility to the central server.
Case 1: Infinite Lists
Lets take your first and second models and mix them into a new one. You want each user to maintain individual state but also want to decrease the load on the main server. Simple, organize the data in reverse-chronological order and only allow your users to access it in that order.
For example, in the original model lets say you have two users. One who is constantly updating to the latest and one who updates twice a year. The response to the person who constantly syncs is pretty small because their state is pretty consistent with the master data set. OTOH. the other user needs to update a massive amount of data after each request to maintain a consistent state with the server.
In the hybrid model, who cares if users have consistent state with the host. Just give them the most recent, if they want more give them the most recent after that, and so on. Worst case, everybody keeps requesting data until eventually their dataset is 100% consistent with the server. In the usual case, they'll only care about the most recent changes which means that the data being made available to the public is essentially a subset of the whole.
A smaller footprint means warm caches, quicker lookups, and lighter weight responses. This is the basic model that most news organizations and social media use today. You have a blog archive that stretches back to 1992, who cares... 99% of your users only want to read the stuff you've written in the past month. Reddit likes to hug 5 of your articles while the internet as a whole ignores the rest, then add frequency analysis to your cache expiration model. Warm caches mean faster lookups which is where your bottleneck will be if you manage to reach scales large enough to care about this sort of stuff.
Case 2: Peer-to-Peer Win
Lets say you actually want your data to be 100% consistent with the host and we're talking about a lot of data. Even if you manage to implement delta updates, if your local copy is far out of sync (or starting fresh) you'll still have a long ways to go.
The answer is simple. Divide and conquer. All you need to do is find a way to break up the data into logical chunks (ex split the data into 10MB chunks), create a map of the hashes of that data for quick/easy lookup/comparison.
OK, now you can request the data from the server in chunks but what if you wanted to go even faster. The answer is simple, separate the hashmap and the actual data into different pieces, de-centralize the host to make every connected node a host, and allow every node to download chunks from every other node.
It's very difficult to scale data transfers when you have a bunch of nodes pulling data from a central point but if everybody is fetching data from everybody, scalability becomes a non-issue.
Want to super-charge downloads. Simple. Request random chunks and for every time a chunk is requested but not available, it's priority increases. That ensures maximum diversity across hosts so there will be no bottleneck on any specific chunk of data.
Sound familiar? It should, what I described is the basis for the BitTorrent protocol. That's why 5 thousand people all downloading the same 2GB movie can still manage to do so at very data transfer rates. It's also why taking down one, or five, or 10 hosts still doesn't kill the swarm. All nodes in the swarm are constantly in communication with other nodes of the swarm but not necessarily every other node, just enough of them to keep the download going. Network communications don't get much more de-centralized or fault-tolerant than that.
As for your 'Chess' example. I know a lot of people like to romanticize about the compexity of chess by talking about the large number of possible combinations. In reality the number of variables involved is so small that the problem domain is practically insignificant.
You're talking about 64 possible spaces on a board and 32 possible pieces for each space. If you compress the pieces down into a bitmap where every piece represents a single bit. That means it takes 64 32-bit words or 256 bytes of data. To put the scale into perspective, there is more data contained in this sentence than there are possible combinations on a chess board.
Even if you make all of the clients 'dumb' (which isn't necessary considering the simple rule set) and isolate all business logic to a central server, the problem doesn't become any more difficult.
Here's the process flow for a 'dumb client' model:
- Client sends move to host
- Host updates global state
- Host published new global state to players
- Players update their board to match
- Rinse & Repeat
As with most things in programming, if you choose an appropriate data structure the code will practically write itself.
Now, consider what it takes to represent than something like a first person shooter where 3-dimensional body positions and bullet trajectories are being calculated and propagated to multiple players in real-time. Ever wonder why you die a lot more when you're lagging? It's because those calculations need to take place on the host server to be accurately synchronized with the game time. A slow connection to the game host will always be a disadvantage, no matter how skilled a player is.
Aside: You could further compress the digital word format used to represent board pieces. By limiting it to only one bit for each piece type. 6 different types of pieces plus a sign bit to mark a piece as either black or white. That means a piece can be effectively represented by a 8-bit (ie rounded up, to the closest byte boundary) word. Which means the data being communicated literally takes up less space than the following ASCII art.
8 ║♜♞♝♛♚♝♞♜
7 ║♟♟♟♟♟♟♟♟
6 ║… … … … … … … …
5 ║… … … … … … … …
4 ║… … … … … … … …
3 ║… … ♘… … … … …
2 ║♙♙♙♙♙♙♙♙
1 ║♖… ♗♕♔♗♘♖
╚═══════════════
a b c d e f g h
Source: http://recessiondodgetovictory.wordpress.com/2011/01/12/ascii-chessboard/
In fact, you could literally just use a 2-D array of UTF-8 chess characters to track the game state.
