Breaking matchmaking deadlocks

[Blair Holloway]

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

[Conor Stokes]

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 <***@chaosandcode.com>
To: sweng-***@midnightryder.com
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

[Blair Holloway]

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 <

Post by Conor Stokes
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
------------------------------
*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.
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[James Robertson]

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.

Post by Blair Holloway
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
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
------------------------------------------------------------------------
*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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
------------------------------------------------------------------------
_______________________________________________
Sweng-Gamedev mailing list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[Morten Brodersen]

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: sweng-gamedev-***@lists.midnightryder.com
[mailto:sweng-gamedev-***@lists.midnightryder.com] On Behalf Of
James Robertson
Sent: Thursday, 8 July 2010 6:13 PM
To: sweng-***@midnightryder.com
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.

Post by Blair Holloway
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!
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

Post by Blair Holloway
request away; therefore, they end up becoming doubly connected to one
another.
- Blair
On Thu, Jul 8, 2010 at 3:14 PM, Conor Stokes
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

Post by Blair Holloway
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

------------------------------------------------------------------------

Post by Blair Holloway
*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

Post by Blair Holloway
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

Post by Blair Holloway
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryde
r.com
----------------------------------------------------------------------
--
_______________________________________________

http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.
com
_______________________________________________
Sweng-Gamedev mailing list Sweng-***@lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.
com

[James Robertson]

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.

Post by Morten Brodersen
A general comment: using real-time clocks to syncronize a distributed
algorithm simply doesn't work in all cases.
http://en.wikipedia.org/wiki/Lamport_timestamps
Morten
-----Original Message-----
James Robertson
Sent: Thursday, 8 July 2010 6:13 PM
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.

Post by Blair Holloway
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

Post by Blair Holloway
works if both machines join each other's games simultaneously. Let me
demonstrate with ASCII!
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

Post by Blair Holloway
and receiving the result -- they can't know to turn the other

machine's

Post by Blair Holloway
request away; therefore, they end up becoming doubly connected to one
another.
- Blair
On Thu, Jul 8, 2010 at 3:14 PM, Conor Stokes
Maintain a shared set of connections (in a hash or something) for
both in-coming and out-going (hunting and gathering), protected by

a

Post by Blair Holloway
lock and keyed by user. Then don't allow inserts/drop the

connection

Post by Blair Holloway
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

Post by Blair Holloway
up with an inconsistent set between players.
Cheers,
Conor

------------------------------------------------------------------------

Post by Blair Holloway
*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

Post by Blair Holloway
with our upcoming title, we're going to adopt a matchmaking

solution

Post by Blair Holloway
- 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

Post by Blair Holloway
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

Post by Blair Holloway
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

Post by Blair Holloway
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

Post by Blair Holloway
system described in Halo 3 seems to randomly decide at the start

of

Post by Blair Holloway
matchmaking whether a machine is a hunter or a gatherer, and

simply

Post by Blair Holloway
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

Post by Blair Holloway
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryde
r.com
----------------------------------------------------------------------
--
_______________________________________________

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

[Philip Taylor]

Post by James Robertson
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.

If you just want a meaningless number with minimal chances of a
collision, timestamps sound like one of the worst possible choices -
people put a lot of effort into making clocks accurate and
synchronised, but you'll get more collisions as they get more
accurate. And once you get one collision, it's much more likely that
you'll get another collision when you try again a little later. An
n-bit random ID (seeded by more than just the timestamp) would have a
much lower chance of collision than an n-bit timestamp.

[Peter Thierolf]

Why not use the MAC address ? That is supposed to be unique anyway...

Post by Philip Taylor

Post by James Robertson
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.

If you just want a meaningless number with minimal chances of a
collision, timestamps sound like one of the worst possible choices -
people put a lot of effort into making clocks accurate and
synchronised, but you'll get more collisions as they get more
accurate. And once you get one collision, it's much more likely that
you'll get another collision when you try again a little later. An
n-bit random ID (seeded by more than just the timestamp) would have a
much lower chance of collision than an n-bit timestamp.

[Blair Holloway]

Having thought about it, each user *does* have a unique ID akin to a MAC
address. Perhaps all we need to break the deadlock is something like:

bool shouldAcceptIncomingConnectionFrom(USERID fromUser) {
if (NotAttemptingConnectionTo(fromUser))
return true;
else if (this->localUserId < fromUser)
return true;
else
return false;
}

I do worry about the implications of relying on a user's id, though -- I
sense it is one of those things that, handled incorrectly, could generate
one of those reproducible-once-in-a-thousand-times bugs. :/

- Blair

Post by Peter Thierolf
Why not use the MAC address ? That is supposed to be unique anyway...

Post by Philip Taylor

Post by James Robertson
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.

If you just want a meaningless number with minimal chances of a
collision, timestamps sound like one of the worst possible choices -
people put a lot of effort into making clocks accurate and
synchronised, but you'll get more collisions as they get more
accurate. And once you get one collision, it's much more likely that
you'll get another collision when you try again a little later. An
n-bit random ID (seeded by more than just the timestamp) would have a
much lower chance of collision than an n-bit timestamp.

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

[James Robertson]

Yes, pretty much any meaningless number can be used. The reason I suggested using a timestamp is so that the player who started attempting to connect first would be the one more likely to succeed. Which isn't a huge deal in the grand scheme of things, but does appeal to my own personal (and slightly warped) sense of order.

Post by Blair Holloway
Having thought about it, each user *does* have a unique ID akin to a MAC
bool shouldAcceptIncomingConnectionFrom(USERID fromUser) {
if (NotAttemptingConnectionTo(fromUser))
return true;
else if (this->localUserId < fromUser)
return true;
else
return false;
}
I do worry about the implications of relying on a user's id, though -- I
sense it is one of those things that, handled incorrectly, could
generate one of those reproducible-once-in-a-thousand-times bugs. :/
- Blair
Why not use the MAC address ? That is supposed to be unique anyway...
On Thu, Jul 8, 2010 at 10:41 AM, James
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.
If you just want a meaningless number with minimal chances of a
collision, timestamps sound like one of the worst possible choices -
people put a lot of effort into making clocks accurate and
synchronised, but you'll get more collisions as they get more
accurate. And once you get one collision, it's much more likely that
you'll get another collision when you try again a little later. An
n-bit random ID (seeded by more than just the timestamp) would have a
much lower chance of collision than an n-bit timestamp.
_______________________________________________
Sweng-Gamedev mailing list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
------------------------------------------------------------------------
_______________________________________________
Sweng-Gamedev mailing list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[Jon Watte]

Personally, I've used the IP address of the nodes as the tie breaker. It's
guaranteed unique, and it's guaranteed consistent, assuming that each box
tells the other box what IP address *it* sees (so that you don't use the
local, inside-NAT interface address).

Somewhat related: for Xbox Live Indie Games, you don't have access to
Live!(tm) Leaderboards(tm), so I have written a component that emulates it
using a gossip protocol over random matchmaking, similar to that Halo
approach. In this particular case, I first try to find a suitable match
using matchmaking and attempting to join, and if that doesn't work, create a
session. This ends up creating the right number of sessions vs players, as
long as you have a reasonable new player join/leave rate, and it's really
simple and robust. The data flowing over the connection is highscores,
rather than gameplay controls, but the mechanism really is the same.

There's one corner case, that I presume is what you're trying to avoid by
both hunting and hosting at the same time: If there are only two players in
the world, and they both try to start a game at almost exactly the same
time, they'll both end up creating sessions and not talking to each other.
However, in practice, this isn't a big deal -- the only thing I do to
mitigate this is to make the amount of time I try hosting a session before
going back to searching be random. That way, one of the two in that bad
example would end up joining the session of the other. More realistically,
if you have any real amount of users, there will be enough churn that
everybody will be paired up in the appropriate host/player ratio.

Sincerely,

jw

--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.

Post by James Robertson
Yes, pretty much any meaningless number can be used. The reason I
suggested using a timestamp is so that the player who started attempting to
connect first would be the one more likely to succeed. Which isn't a huge
deal in the grand scheme of things, but does appeal to my own personal (and
slightly warped) sense of order.

[Blair Holloway]

You presume correctly - it's that corner case I'm trying to avoid; but as
you describe, having a player host an empty match for a random amount of
time before returning to searching should be enough to ensure it doesn't
become too big an issue.

Of course, we won't really know if we have enough churn to avoid the problem
entirely until we launch... J

Post by Jon Watte
Personally, I've used the IP address of the nodes as the tie breaker. It's
guaranteed unique, and it's guaranteed consistent, assuming that each box
tells the other box what IP address *it* sees (so that you don't use the
local, inside-NAT interface address).
Somewhat related: for Xbox Live Indie Games, you don't have access to
Live!(tm) Leaderboards(tm), so I have written a component that emulates it
using a gossip protocol over random matchmaking, similar to that Halo
approach. In this particular case, I first try to find a suitable match
using matchmaking and attempting to join, and if that doesn't work, create a
session. This ends up creating the right number of sessions vs players, as
long as you have a reasonable new player join/leave rate, and it's really
simple and robust. The data flowing over the connection is highscores,
rather than gameplay controls, but the mechanism really is the same.
There's one corner case, that I presume is what you're trying to avoid by
both hunting and hosting at the same time: If there are only two players in
the world, and they both try to start a game at almost exactly the same
time, they'll both end up creating sessions and not talking to each other.
However, in practice, this isn't a big deal -- the only thing I do to
mitigate this is to make the amount of time I try hosting a session before
going back to searching be random. That way, one of the two in that bad
example would end up joining the session of the other. More realistically,
if you have any real amount of users, there will be enough churn that
everybody will be paired up in the appropriate host/player ratio.
Sincerely,
jw
--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.

Post by James Robertson
Yes, pretty much any meaningless number can be used. The reason I
suggested using a timestamp is so that the player who started attempting to
connect first would be the one more likely to succeed. Which isn't a huge
deal in the grand scheme of things, but does appeal to my own personal (and
slightly warped) sense of order.

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

[Blair Holloway]

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.

Post by Morten Brodersen
A general comment: using real-time clocks to syncronize a distributed
algorithm simply doesn't work in all cases.
http://en.wikipedia.org/wiki/Lamport_timestamps
Morten
-----Original Message-----
James Robertson
Sent: Thursday, 8 July 2010 6:13 PM
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.

Post by Blair Holloway
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

Post by Blair Holloway
works if both machines join each other's games simultaneously. Let me
demonstrate with ASCII!
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

Post by Blair Holloway
and receiving the result -- they can't know to turn the other

machine's

Post by Blair Holloway
request away; therefore, they end up becoming doubly connected to one
another.
- Blair
On Thu, Jul 8, 2010 at 3:14 PM, Conor Stokes
Maintain a shared set of connections (in a hash or something) for
both in-coming and out-going (hunting and gathering), protected by

a

Post by Blair Holloway
lock and keyed by user. Then don't allow inserts/drop the

connection

Post by Blair Holloway
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

Post by Blair Holloway
up with an inconsistent set between players.
Cheers,
Conor

------------------------------------------------------------------------

Post by Blair Holloway
*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

Post by Blair Holloway
with our upcoming title, we're going to adopt a matchmaking

solution

Post by Blair Holloway
- 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

Post by Blair Holloway
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

Post by Blair Holloway
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

Post by Blair Holloway
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

Post by Blair Holloway
system described in Halo 3 seems to randomly decide at the start

of

Post by Blair Holloway
matchmaking whether a machine is a hunter or a gatherer, and

simply

Post by Blair Holloway
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

Post by Blair Holloway
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryde
r.com
----------------------------------------------------------------------
--
_______________________________________________

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

[Alen Ladavac]

_______________________________________________
Sweng-Gamedev mailing list
Sweng-***@lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[Rex Guo]

Here are some slides and demo on games networking from GDC10
in which it covers the topic of tie-breaking in situations similiar to this.

Might be of some help...

http://gafferongames.com/

.rex

When I see this kind of chicken/egg problem I usually first think of
Assign a unique ID to each machine (GUID, XUID, whatever), and make sure it
is communicated both ways when connecting. Each machine, if it detects it
has duplicate connections to some other machine, drops that connection from
the pair where the server side of the connection has lower UID than the
client side.
c1: A=server, B=client
c2: B=server, A=client
Since 123<456, both machines simultaneously drop c1. Et voilà.
Does the explanation make sense? I haven't actually used this in practice
for this particular use case, but it works fine for some other
single-machine problems of similar nature.
HTH,
Alen
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 <
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
------------------------------
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.
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
--
Alen
_______________________________________________
Sweng-Gamedev mailing list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[Mat Noguchi]

Why not have a separate task that is for the hunter/gather hybrid? When two hybrid tasks connect, you can then break the tie and convert one into a hunter and the other into a gather. If a gather connects to a hybrid, the hybrid should convert to a hunter, and if a hunter connects to a hybrid, the hybrid should convert to a gather.

MSN
From: sweng-gamedev-***@lists.midnightryder.com [mailto:sweng-gamedev-***@lists.midnightryder.com] On Behalf Of Blair Holloway
Sent: Thursday, July 08, 2010 1:02 AM
To: sweng-***@midnightryder.com
Subject: Re: [Sweng-Gamedev] Breaking matchmaking deadlocks

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 <***@yahoo.com<mailto:***@yahoo.com>> 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 <***@chaosandcode.com<mailto:***@chaosandcode.com>>
To: sweng-***@midnightryder.com<mailto:sweng-***@midnightryder.com>
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

[Blair Holloway]

If I understand you correctly, once the machines connect, regardless of the
result, each machine goes into a passive state - the hunter no longer needs
to hunt (it's connected), and the gatherer is, well, gathering. (Gathered?)

Let's say your target session size is four machines; once you're connected
to someone, you stop being a hybrid, and you are either a gatherer,
listening for more machines, or are essentially idle. How do you deal with
these cases, where the machines have essentially "paired off", and you want
to coalesce them into larger sessions? Would it not be more beneficial to
keep some machines as hybrids?

Post by Mat Noguchi
Why not have a separate task that is for the hunter/gather hybrid? When
two hybrid tasks connect, you can then break the tie and convert one into a
hunter and the other into a gather. If a gather connects to a hybrid, the
hybrid should convert to a hunter, and if a hunter connects to a hybrid, the
hybrid should convert to a gather.
MSN
Holloway
*Sent:* Thursday, July 08, 2010 1:02 AM
*Subject:* Re: [Sweng-Gamedev] Breaking matchmaking deadlocks
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 <
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
------------------------------
*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.
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
_______________________________________________
Sweng-Gamedev mailing list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[Mat Noguchi]

Ah... I see what you are saying. I suppose that you want one of the hybrid keep looking if you initially paired up hybrids.

MSN
From: sweng-gamedev-***@lists.midnightryder.com [mailto:sweng-gamedev-***@lists.midnightryder.com] On Behalf Of Blair Holloway
Sent: Thursday, July 08, 2010 6:56 PM
To: sweng-***@midnightryder.com
Subject: Re: [Sweng-Gamedev] Breaking matchmaking deadlocks

If I understand you correctly, once the machines connect, regardless of the result, each machine goes into a passive state - the hunter no longer needs to hunt (it's connected), and the gatherer is, well, gathering. (Gathered?)

Let's say your target session size is four machines; once you're connected to someone, you stop being a hybrid, and you are either a gatherer, listening for more machines, or are essentially idle. How do you deal with these cases, where the machines have essentially "paired off", and you want to coalesce them into larger sessions? Would it not be more beneficial to keep some machines as hybrids?

On Fri, Jul 9, 2010 at 4:32 AM, Mat Noguchi <***@bungie.com<mailto:***@bungie.com>> wrote:
Why not have a separate task that is for the hunter/gather hybrid? When two hybrid tasks connect, you can then break the tie and convert one into a hunter and the other into a gather. If a gather connects to a hybrid, the hybrid should convert to a hunter, and if a hunter connects to a hybrid, the hybrid should convert to a gather.

MSN
From: sweng-gamedev-***@lists.midnightryder.com<mailto:sweng-gamedev-***@lists.midnightryder.com> [mailto:sweng-gamedev-***@lists.midnightryder.com<mailto:sweng-gamedev-***@lists.midnightryder.com>] On Behalf Of Blair Holloway
Sent: Thursday, July 08, 2010 1:02 AM

To: sweng-***@midnightryder.com<mailto:sweng-***@midnightryder.com>
Subject: Re: [Sweng-Gamedev] Breaking matchmaking deadlocks

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 <***@yahoo.com<mailto:***@yahoo.com>> 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 <***@chaosandcode.com<mailto:***@chaosandcode.com>>
To: sweng-***@midnightryder.com<mailto:sweng-***@midnightryder.com>
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

[Richard Fabian]

Solving the deadlock:
Maybe you just need the doubly connected pair to keep playing a different
game with each other until they decide who should be the host...

A->B high roll game (d20)->13
B->A high roll game (d20)->13
... ooh, same, play again
A->B high roll game (d20)->5
B->A high roll game (d20)->20 (critical network hit ;)
B wins, becomes the decider of who should be host and who should be client.

I think this is simple, and effective. So what, if you have to go around
five times before you make a decision, at least you can make a decision now.

Post by Blair Holloway
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com