Re: Breaking matchmaking deadlocks

Interesting concept! Using a logical clock would seem to swap one problem
for another, though: instead of having identical timestamps, you can still
get collisions between identical logical clock values.

On Thu, Jul 8, 2010 at 7:19 PM, Morten Brodersen <[email protected]> wrote:

> 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
>

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