Hi everyone,

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.

Since the list sits on one phone and that acts as the server, I'd just let the other phone ask if it's ok to remove a word and wait for the server's reply before continuing. I don't think you need actual locks to implement this.

Isn't that in essence a locking mechanism? The host phone will need to be aware of who is accessing resources, and block the other phone.

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. :)

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!

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!

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.

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.

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.

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.