Re: Breaking matchmaking deadlocks

A general comment: using real-time clocks to syncronize a distributed
algorithm simply doesn't work in all cases.

You need a logical clock or something similar. More info here:

http://en.wikipedia.org/wiki/Lamport_timestamps

Morten

-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of
James Robertson
Sent: Thursday, 8 July 2010 6:13 PM
To: [email protected]
Subject: Re: [Sweng-Gamedev] 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-midnightryde
> r.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

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