Re: Breaking matchmaking deadlocks
James Robertson <[email protected]> Thu, 08 Jul 2010 11:41:22 +0200
| Newsgroups | gmane.games.devel.sweng |
|---|---|
| Message-ID | <[email protected]> |
True, but in this case it really doesn't matter. All you're looking for is a way to reject one connection and keep the other, with a fallback for the (extremely) rare instances that both times are identical. The timestamps could be years apart and the mechanism would still give the required result. Morten Brodersen 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