Now, the problem is that my SLA does not allow 3 to block 4--persistence in this case takes too long and the client needs to know right away that the request has succeeded (this is the standard use case for the 202
http status code).
But until the state change is persisted, you can't know that you're successful. You might have a sudden problem with electrical power and an errant backhoe (this stuff happens!) and then when the service resumes, it's completely forgotten about the resource. The client comes back and the server has no idea what its talking about. That's not good.
No, you need to speed up commits (and avoid unnecessary processing in the critical path).
You may need to think about how you can logically commit faster, about what it means to commit; you can just commit the fact that there is work to do instead of having to require the result of the work, which can be done much more rapidly. Then when the user comes back, either the processing is done in which case you can 301 to the results, or you can give a result that says why things are still processing or that they've failed.
Getting faster commits might mean thinking more carefully about how you deploy. Are you using the right database choice? Is that database hosted on the right hardware? (Commit-heavy loads are much faster when you've got an SSD to host the transaction log on.) I know it's nice to ignore these things and just deal with the data model at an abstract level, but performance is one of those things where the underlying details have a habit of leaking through.
In response to comments clarifying…
If you've got a genuinely expensive task to perform (e.g., you've asked for a collection of large files to be transferred from some third party) you need to stop thinking in terms of having the whole task complete before the response comes back to the user. Instead, make the task itself be a resource: you can then respond quickly to the user to say that the task has started (even if that is a little lie; you might just have queued the fact that you want the task to start) and the user can then query the resource to find out whether it has finished. This is the asynchronous processing model (as opposed to the more common synchronous processing model).
There are many ways to handle letting the user know that the task has finished. By far the simplest is to just wait until they poll and tell them then. Alternatively, you can push a notification somewhere (maybe an Atom feed or by sending an email?) but these are much trickier in general; push notifications are unfortunately relatively easy to abuse. I really advise sticking to polling (or using cleverness with websockets).
The case where a task might be quick or might be slow and the user has no way to know ahead of time is really evil. Unfortunately, the sane way to resolve it is to make the processing model be asynchronous; it's possible to do either way flipping with REST/HTTP (it's either sending a 200 or a 202; the 202's content would include a link to the processing task resource) but it is quite tricky. I don't know if your framework supports such things nicely.
Be aware that most users really do not understand asynchronous processing. They do not understand having to poll for results. They do not appreciate that a server can be doing things other than handling what they asked it to do. This means that if you are serving up an HTML representation, you probably ought to include some Javascript in it to do the polling (or connecting to a websocket, or whatever you choose) so that they can not need to know about page refreshing or details like that. Like that you can go a long way towards pretending that you're just doing what they asked it to do, but without all the problems associated with actual long-running requests.
In general, it turns out very badly if objects of the same level know about each other. Once objects know about each other they are tied, or coupled to each other. This makes them hard to change, hard to test, hard to maintain.
It works out much better if there is some object "above" that knows about the two and can set the interactions between them. The object that knows about the two peers can tie them together via dependency injection or via events or via message passing (or any other of decoupling mechanisms). Yes, that leads to a bit of an artificial hierarchy, but it's far better than the spaghetti mess that you get when things just interact willy-nilly. That is only more important in C++, since you need something to own the lifetime of the objects too.
So in short, you can do it by just having objects side by side everywhere tied together by ad hoc access, but it's a bad idea. The hierarchy provides order and clear ownership. The main thing to remember is that objects in code are not necessarily objects in real life (or even the game). If the objects in the game don't make a good hierarchy, a different abstraction may be better.
Best Answer
It's the easiest if you have a "mothership". Nowadays it doesn't have to be a single server, a SPOF, there are tons of cheap CDN (content delivery network) and cloud solutions.
Otherwise, borrow an idea from a software that is the most successful: bittorrent. Distributed hash tables (DHT) are simply beautiful. And if I'm not mistaken, you can piggyback your own software on the DHT network. DHT doesn't have to be bittorrent-specific, but there are millions of hosts in the bittorrent DHT network already, so why not use it for anything that you like? It's a huge free resource, the protocol is trivial, but there are already lots of libraries for it, it's like a gold mine.
Of course, DHT needs to be bootstrapped as well, but it's an already solved problem. You can collect a big list of known DHT hosts, or just probe randombly, it is so huge that either can work.
Bittorrent's DHT is simple: every torrent has a hash, and the DHT network stores a peer list for each hash. All you have to do is make up a fake, fixed hash for your needs and store that in the DHT. You can help bootstrapping if you create a few DHT nodes yourself that are close to your fixed hash, but it won't be necessary.
Well, it's actually not a completely free resource, if you participate in the DHT network, then you should also participate in the storage of other hashes, and other peers will use your peers as a service.