I am working on an online multiplayer game with around half a dozen players. The player who first starts a match acts as the server. So there are NO dedicated servers. Now when the server leaves, I need to elect another player's computer to act as the server. I would like this to happen as smoothly as possible. So I need an algorithm to automatically select another server. My question is: which algorithm should I use for this?

Since this is online multiplayer, the algorithm needs to be robust under weird situations. For example, maybe the server disconnects and at the same time one of the other players disconnects as well. Or maybe the server disconnects, another player is chosen as server, and that player immediately disconnects as well. The algorithm must always find a correct result, even in such rare situations.

Also, the game plays fully connected. So if there are five players, then each player is connected to each other player. However, some of these connections may not be established. However, as long as a player is connected to the server, he can still play. So the server that is chosen should at least have a connection to all the remaining players. From those computers that satisfy this requirement, I would like to choose the computer with the lowest average ping or something like that.

I am supposing there are standard algorithms for this, which would you advice?

Thanks in advance! :)

Hi!

I'm no expert, but the way I would do it is by having everyone ping everyone.
For simplicity, I wouldn't ping N^N times, but rather N! times since I would assume
ping( A to B ) * 2 = ping( A to B ) + ping( B to A )

(I would like to know from a true expert if making this assumptions is horrible wrong).

Then send the results to the current server, make this server get the statistical mode and chose the new server.
If reliability is what you're after, then someone else (redundancy) besides the current server should get the information to make this decision in case the server goes down while choosing (may be send the info to everyone? so everyone has it?)

Note this isn't easy at all, it assumes all your clients have open incoming ports; which is a downside of P2P, while the advantage of a client-server architecture is that only the server has to deal with firewalls, port forwarding configuration, etc.

Unfortunately measuring from the server alone which of it's clients has the lowest ping is useless, as this client may have a low ping with that particular server, but all the other clients have an awful ping response time to that particular client.

Ideally the best server is the one that lies equidistant from all clients

I would save the average response time for each client and pick the client with the lowest for server selection.

I just learned via another route that there is actually a much easier solution: PS3, 360 and Steam all have automatic mechanisms for this, which I can simply use. :)

As for the solutions proposed here: none of them really seem to handle the rare cases. For example, if you synch ping times over the network to choose the best server. That in itself is not very difficult. But what if the server disconnects while it was halfway in sending the clients the ping times. Now some clients may have the newest information and conclude that client A is to be the new server, while other clients may still have older information and conclude that client B is to be the new server.

Glad PS3/360/Steam will handle those really difficult cases for me! :)

Generally, when you connect to a server, that server can also inform everyone of what the next back-up server is. If the first server dies before this happens, then the session simply didn't initiate.

Each peer will then try to connect the next server in the list, going down the list, until it's connected to *someone* in the group. If that *someone* has a better idea of who is the new server, the connecting peer can then re-direct to the new server.

Of course, if you're using middleware (Live!, Steam, etc), then let the middleware deal with it :-)