Breaking matchmaking deadlocks

Rather than taking the typical "join session/host session" approach with our
upcoming title, we're going to adopt a matchmaking solution - the user
selects the "find players" option, and under the covers the game deals with
creating and joining as necessary.

We've been examining the matchmaking system described in "E Pluribus Unum:
Matchmaking in HALO 3"[1], and decided to take a similar approach -- when
matchmaking begins, a "gatherer" task hosts a session, and waits for players
to connect to it, whilst a "hunter" task enumerates a list of sessions and
tries to join each in turn.

Since these tasks happen simultaneously, it's possible to end up in a
quasi-deadlock -- the hunter task from machine A can connect to the
gatherer's session on machine B, whilst machine B's hunter simultaneously
connects to machine A's gatherer; both machines would be simultaneously
hosting two sessions, and each machine would be participating in both.

The easiest solution to this is perhaps to avoid the "deadlock" in the first
place, and not simultaneously search and host. Indeed, the system described
in Halo 3 seems to randomly decide at the start of matchmaking whether a
machine is a hunter or a gatherer, and simply sticks to that choice until a
timeout occur.

However, Halo has the advantage of a huge player base to make this work;
we're expecting a few orders-of-magnitude less players, and are worried that
when, say only a few tens of people are online at any given time, only
gathering or hunting will make the matchmaking experience slow for the user.
Therefore, we'd like to both gather and hunt at the same time, and try to
avoid the deadlocks and "break" them when they occur -- i.e. when detecting
simultaneous connections, choose one session to destroy, whilst keeping the
other.

Does anyone have any suggestions for how to break these "deadlocks"?

Cheers,

- Blair

[1]
http://www.bungie.net/images/Inside/publications/presentations/gdc2008_butcher_chris_matchmaking.ppt

_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com