Re: Breaking matchmaking deadlocks

If your join requests have timestamps, you can reject a join request from A if you have already requested to join A's game and the time your request was sent was before A sent his.  In the remote possibility that two requests are sent at *exactly* the same time you reject as well and let each client retry.  Eventually one will succeed and the other will fail.



Blair Holloway wrote:
> For sure, rejecting a duplicate connection like this will work in cases 
> where the connection is fully established. However, I'm not sure that it 
> works if both machines join each other's games simultaneously. Let me 
> demonstrate with ASCII!
> 
> (If the formatting is stuffed, try pastebin: http://pastebin.com/U1YP7Ain)
> 
> A -----a---c---*
>         \ / \ /
>          X   X
>         / \ / \
> B -----b---d---*
> 
> A = machine A's timeline
> B = machine B's timeline
> 
> a = machine A sends request to join machine B's game
> b = machine B sends request to join machine A's game
> c = machine A receives request to join from machine B, accepts, sends 
> back response
> d = machine B receives request to join from machine A, accepts, sends 
> back response
> 
> * = both machines suddenly realise that they are connected to each 
> other's games
> 
> Because each machine is responding to each other's join requests in 
> their "cone of silence" -- the time between their request to join a game 
> and receiving the result -- they can't know to turn the other machine's 
> request away; therefore, they end up becoming doubly connected to one 
> another.
> 
> - Blair
> 
> On Thu, Jul 8, 2010 at 3:14 PM, Conor Stokes 
> <[email protected] 
> <mailto:[email protected]>> wrote:
> 
>     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]
>     <mailto:[email protected]>>
>     *To:* [email protected]
>     <mailto:[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]
>     <mailto:[email protected]>
>     http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Sweng-Gamedev mailing list
> [email protected]
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com