Re: Breaking matchmaking deadlocks

Maintain a shared set of connections (in a hash or something) for both in-coming 
and out-going (hunting and gathering), protected by a lock and keyed by user. 
Then don't allow inserts/drop the connection into the shared set if you find a 
connection already there. It's a small relatively constant time operation and 
you should be able to set it up for the right order of operations such that you 
won't end up with an inconsistent set between players. 

Cheers,
Conor 



________________________________
From: Blair Holloway <[email protected]>
To: [email protected]
Sent: Thu, 8 July, 2010 10:50:25 AM
Subject: [Sweng-Gamedev] 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