A Simple Nonblocking Solution Assuming Atomic Integers

From Beautifulcode

First, we create simple, non-blocking mechanism to distribute tiles, assuming that ints are atomic. The distributor contains two members:

1. valid_ordinals: An array of ints equal to the number of tiles that will be distributed per player (in this case, 8); valid_entries is initialized to zero and is used to determine if a particular tile entry is available. 2. ordinal_tile: An two dimensional array of characters equal to the number of tiles distributed per player x the number of players. This array is initialized before the game is run.

The distributor supports two operations:

1. mark_valid_tile: Given a tile ordinal, the distributor will mark that ordinal as valid: valid_ordinals[tile_ordinal]= 1.

2. try_to_get_tile: Given a tile ordinal (i.e., the next tile a player wants to receive) and a player ordinal, it tries to grab the tile for that ordinal, and returns true if successful and false otherwise: if (valid_ordinals[tile_ordinal]!=0) out_tile= ordinal_tile[tile_ordinal][player_ordinal]; success= true;

Next, we have a distributor per player. It has three members:

1. A player ordinal (constant). 2. A tile ordinal. 3. A distributor to grab tiles from.

It has one operation:

1. A parameterless operation that tries to grab the next tile and updates the tile ordinal if successful: if (distributor.try_to_get_tile(next_tile_ordinal, player_ordinal, out_tile)) ++next_tile_ordinal; success= true;

Now, we also need something to collect answers. Although the implementation depends on how much we trust players, it needs at least three members:

1. A distributor to mark valid tile solutions. 2. The player ordinal of the player that uses it. 3. A timestamp for the final solution.

And one operation:

1. submit_solution: Takes a solution for N-tiles, validates it, and marks that tile as good, and records the necessary information to determine the winner if it is the final solution: if (solution.get_tile_count()==k_tile_count) potential_winning_time= now(); if (valid_solution(solution)) distributor.mark_valid_tile(solution.get_tile_count()); if (solution.get_tile_count()==k_tile_count) winning_time= potential_winning_time;

We can package up the per-player distributor and per-player validator into a single object that we give each player.

The whole game then proceeds as such:

The referree initializes an instance of the tile distributor (which pre-generates the set of tiles that will be distributed to each player), then creates a distributor/validator object for each player and assigns an player ordinal to each. Each player then runs until they are all done, and the referree can query the winning time from each validator to determine the winner.

How do we guarantee that it actually works? In no particular order:

1. The per-player distributor ensures that any player will only get tiles up to and including the highest valid solution, assuming that we mark only valid N-tile solutions.

2. The tile distributor will work correctly regardless of what order valid solutions are marked in (assuming that an N-tile solution does not arrive before any (N-M)-tile solution for any M<N). Since the valid tile ordinal is determined by indexing into an array of (essentially) boolean values and not a counter of the highest solution, we don't need to worry about ordering of solution submission.

3. If we want to guard against malicious players, we can combine the per-player distributor and validator to ensure that solutions match the tiles that have actually been distributed so that players cannot attempt to generate random tiles to submit a 15-letter solution.

4. Since getting a tile is based on state and not a synchronization object, any time a valid solution is marked in the distributor by any player it is immediately available for all players to access. In other words, access is not bounded by a single thread updating, it is bounded by any thread marking a solution as valid.

The beauty of this system lies in the simplicity and performance: there are no deadlocks as the only communication mechanism is an array of integers; there is no overhead beyond properties of the computer architecture the system runs on. There is potential for livelock if the validator's valid_solution operation can spin, but that can be alleviated by running submit_solution on a separate thread (one per player per tile ordinal), and blocking inside submit_solution if a player attempts to submit more than one solution for a particular tile ordinal. Since we also use the most simple assumption of atomic integers and prepopulate the available tiles per player, we have no need for memory barriers to ensure correct behavior. This system also guarantees that once anyone submits a valid solution, everyone can get another tile. And, this system does not constrain potential player strategies at all; a player can attempt to create a solution for every tile set or just spin on try_to_get_tile until she has 15 tiles and attempt to create a solution from that, or submit the same solution over and over, or any strategy in between, without affecting the performance of any other player. (That of course assumes that every player really runs concurrently.)

On a higher level, this system takes the physical aspect of the tile game (that each player has an unknown but predetermined set of tiles) to create a solution that models what a game in real life would do.