Sign in to follow this  

Handling concurrent random access of shared resource on peer to peer system?

This topic is 486 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone,

 
What would be the best way to handle concurrent random access of a shared resource on a peer to peer* system?
 
My goal is to make a two player word game, and the two players both need to access a shared set of words and characters.
The players can add words/characters and take words/character at random.
 
My idea right now is this:
  1. Have one player host the game, i.e. their phone will act as the host server. The shared resource will sit on their phone. 
  2. Every time a player potentially adds or removes a word/character, they acquire a Java lock on the shared words/characters.
  3. Locks will "wait" for other locks to be removed first. 
  4. Each call to acquire a lock will have to first check if the word they want to remove or add has already been removed or added by the preceding lock.
Is this a good design? I'm a little worried it may cause a slow game.
I'm also at this point not 100% certain it's possible for Player B to acquire a lock on a resource on Player A's phone.
 
I'm thinking I will use sockets for the peer to peer system.
 
Hopefully this is an okay place to post this type of question.
 
Thanks for your help!
 
*perhaps the "peer-to-peer" architecture I'm describing some might still consider to be "client-server"? 
 
p.s. I did perform a search and found threads like the following, but not sure if they are referring to the same thing as I am:
 
 

Share this post


Link to post
Share on other sites

It's a "locking mechanism" in high level concepts, but it's nothing at all like a "lock" in the Java sense.

 

Your proposed use of locks doesn't accomplish anything. Networked code is a little different than multi-threaded code; the other phone simply _can't_ access any objects on the host phone. It's not possible, period. Instead, the other phone must send a request to the host phone asking the host to perform the action. The host can process these actions and the local player's actions all in a single thread.

 

All you really need is a flag of some kind indicating that a word/letter is in use. That flag can just be a boolean or an enumeration. You don't need a lock unless there's the possibility of two threads of execution accessing the flag at the same time.

 

So far as speed, the player on the host phone will definitely have an advantage in terms of latency. This is an unavoidable part of networked code; whoever is closest to the server has the latency advantage. That said, heavy-weight real-time action shooter games manage to get by just fine so your game is unlikely to have a serious problem with speed. Remember, we're talking about _computers_ doing this work, and "slow" to a computer is still basically instantaneous to a human. :)

Share this post


Link to post
Share on other sites

MudMesa,

 

As SeanMiddleditch suggested, you cannot lock resources on other computers directly. However you can create an API which makes it appear as though you have (which is how network filesystems such as NFS, SMB etc... work).

 

I wrote a paper a while back on how to provide and sync a tree-like structure to all clients and allow them to share / lock the resources in a multi-player shooter game. You might find it useful: http://dl.acm.org/citation.cfm?id=2662601

 

If you are working with C++, I might be able to rip the source out of our existing product and share some things.

This stuff is also still very relevant to my PhD so I would be very interested in hearing if you have come up with any of your own nifty solutions to this.

 

Edit: Darn, just noticed that the ACM Digital Library is not open-access and is only accessible behind a University address range or for paid subscribers. I will grab the .pdf paper and upload it on Monday. Sorry!

Edited by Karsten_

Share this post


Link to post
Share on other sites

Thank you for your very helpul suggestions and clarifications! 

 

I'll need to use locks on the flags since the words/letters will be accessed and removed at random, right?

 

Karsten_, thanks for the link and share! For this project I'm working with Java, but I do work with C++ sometimes.

No worries, I'll take a look when you upload it and let you know if I come up with anything!

Share this post


Link to post
Share on other sites

I'll need to use locks on the flags since the words/letters will be accessed and removed at random, right?


No, definitely not; you need locks if there are multiple threads accessing the value. If there are not multiple threads then you do not need locks. The end.

If you do have multiple threads and you're locking individual flags on a tree of objects, overwhelming odds are that you're doing threading horribly horribly wrong and need to completely rethink your entire architecture. Java in particular taught a whole generation of programmers how to do threading HORRIBLY WRONG so you're forgiven if you're thinking you need threads; you 100% do not need them, and you 100% do not _want_ them.

You have a really simple problem here: a player wants to reserve a letter and then later consume it. This is just a flag. This cannot happen with a second thread because the other player is not another thread. Your game loop will look very vaguely something like:

main {
  requests = read_local_commands()
  requests += deque_remote_player_requests()

  for each request in requests {
    if request.reserve {
      letter = letters[request.reserve.letter]  // NO LOCK necessary
      if letter.reserved_by // NO LOCK necessary
        request.failed('letter already reserved')
      else
        letter.reserved_by = request.player_id  // NO LOCK necessary
    }
    if request.use {
      letter = letters[request.reserve.letter]
      if letter.reserved_by != request.player_id 
        request.failed('letter not reserved by you')
      else
        consume_letter(letter)  // NO LOCK necessary
    }
  }

  send_letter_state_to_remote_player()
  draw_letter_state_for_local_player()
}
Are there fancier ways to do this? Of course. SHOULD you use a fancy way to do this? Most likely not.

If you're concerned about the host having a latency advantage, use an authoritative remote server. This also removes the ability for the host to cheat by modifying their local copy of the game.

Share this post


Link to post
Share on other sites

Thanks for helping me rethink this, at first I was definitely thinking of having a separate thread handle the second player's requests.
 
In the pseudocode it looks like local requests are serially processed before remote requests. 
To have requests processed in the order they are spontaneously generated, would one sort the requests by a time stamp? (after serially retrieving the local and remote requests as above) 
 
Going off of the pseudocode, my thought is to set up a loop to repeatedly pull local and remote requests into the requests queue, sort those by time stamp, then process each request serially in the queue. 
 
E.g.

main {
  while(1){
    requests = read_local_commands()
    requests += deque_remote_player_requests()
  
    sort_by_timestamp(requests);

    for each request in requests {
      ...
     }
    send_letter_state_to_remote_player()
    draw_letter_state_for_local_player()
  }
}

Really glad to get some alternate architecture design ideas. This "funnel"/"bottleneck" architecture hadn't crossed my mind.

Edited by MudMesa

Share this post


Link to post
Share on other sites

To have requests processed in the order they are spontaneously generated, would one sort the requests by a time stamp?

Unfortunately, in a distributed world there is more than one clock, and clocks do not run synchronously.

 

 

In your room, find 2 clocks, and compare their times. They will not tell you the same time, often not even within a minute.

At sub-second level which is what we're talking here, don't even bother trying.

 

That means, in a distributed world, you don't know the precise time. Having more than one independent clock breaks that.

 

From an attack point of view, I could exploit your sorting by setting the time of my device back by say, an hour. That means I'd always be the first one in the queue.

 

 

Not that it would change anything in a 2 player game. Think about it. Processing 1 request takes how long? 1msec? How many requests can a player send each second? 2 (would be a very fast player)? So for a 2 player game, you have max 4 requests in a second, each taking 0.001 second to process, which leaves 0.996 second "empty". The chance you get 2 requests at the same time is neglible.

That means your sort isn't doing anything, as you practically never have a queue. I would suggest to just process requests as they come.

 

 

In general, when writing a program, first aim for the simplest possible solution that looks like it will work.

 

If it does work after coding everything, you're done quickly. If it does not, think more, and fix the problem.

The big advantage here is that you don't waste time on solving problems that don't exist in the final application. Also, after you wrote the program, you have a much better view of all the pieces that exist, and how they relate. That puts you in a much better position to decide how to fix a problem. Maybe you can turn a knob at some other part of the program (like limiting the number of characters that a player can request or display an 0.8 second animation when you get a new letter), and the problem disappears like snow.

 

 

For fun, I computed what would happen with 100 players. This is queueing theory with a Poisson arrival pattern, and a single processing server, ie https://en.wikipedia.org/wiki/M/M/1_queue

 

That gives

? = 200     (100 players each doing 2 requests a second).

? = 1000  (1000 requests per second can be processed).

? = ?/? = 200/1000 = 0.2

 

avg = ?/(1 ? ?) = 0.2/0.8 = 0.25

var = ?/(1 ? ?)2 = 0.2/(0.8*0.8) = 0.32

 

The average queue length is 0.25 (slightly more than the 0.2 lower limit you would get if requests never arrive at the same time), The variance gives an impression of how much fluctuation you get on that average. Since a waiting customer happens only for queue lengths > 1 (1 request waiting, and one being processed), even with 100 players you hardly ever get a collision.

Share this post


Link to post
Share on other sites

Right, I have uploaded the paper. It is actually one of my short papers (which I always find very difficult to fit enough information in) but hopefully it might give you some starting point.

 

http://devio.us/~kpedersen/papers/p40-pedersen.pdf

 

Just waiting on permission to release source code. The problem is that the project utilizing this code has been Greenlit on Steam but we haven't been bothered to do anything about it haha.

Edited by Karsten_

Share this post


Link to post
Share on other sites

@Alberth Thanks for the insight! I'll start off with just handling the requests as the come in then. 

I can't say I fully understand the intuition of the calculations yet since I just started taking a look at queueing theory, but I'll take your word for now and keep reading up on it.

 

@Karsten_ , thank you! Yeah shorter papers are always harder to write than longer ones. I'll take a look!

Haha that's cool that it's part of a Greelight game!

Share this post


Link to post
Share on other sites

Thanks for helping me rethink this, at first I was definitely thinking of having a separate thread handle the second player's requests.
 
In the pseudocode it looks like local requests are serially processed before remote requests. 
To have requests processed in the order they are spontaneously generated, would one sort the requests by a time stamp? (after serially retrieving the local and remote requests as above) 
 

 

You could just have a general command queue, where all commands received (either from a remote player, or form a local player) are put into a single FIFO queue.  Then, when you process all the commands in that queue, you'll automatically process them in the order they are received.

 

However, since this should happen every game loop, in practice, there really won't be any difference in what order you handle them.  If you execute your game loop once every 1/60 second (for example), then that would be the largest possible difference in time between when a local play sent you something, and when a remote player sent you something, if processed in order.  And, even then, network delay would probably be larger than that.

 

Good luck, and keep at it.

Share this post


Link to post
Share on other sites

This topic is 486 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this