COMP2310/COMP6310:
Concurrent and Distributed Systems
Semester 2 2013

Assignment 1

A Concurrent Card Game

Deadline: 17:00 on Friday 06 September


(Please report any errors, omissions and ambiguities to the course lecturer)
(Amendments to this document after its release in non-draft will be marked in blue)


This assignment is worth 18% of your total course mark. It will be marked out of 36.

Submission

This assignment must be submitted electronically. This can be done using the following commands (according to your enrollment):

Extensions

See the course Assessment page. Late penalties are as follows:

How LatePenalty from 36 Marks
less than 1 hour-2
between 1 and 6 hours-4
between 6 and 24 hours (1 day)-8
between 24 and 48 hours (2 days)-16
between 48 and 72 hours (3 days)-32
more than 72 hours (4 days)-64 (forget it!)

Note: late penalties apply even if you submit just one file after the deadline.


Objectives

The Card Game

There are P=4 players. From a standard deck of cards you select 24 cards consisting of all P=4 suites and C=6 different kinds, eg the Ace, King, Queen, Jack, 10 and 9 of Clubs, Diamonds, Hearts and Spades. The players are seated around a table. In the centre of the table there are P'=4 piles of cards. The game begins with a dealer, who deals each player P=4 cards, and places n=2 cards on each of the piles. The initial assignment of cards to players and piles is random (i.e. the cards have been shuffled).

When play starts all players begin to (randomly) pick a card from the top of a (non-empty) pile and place it in their hands. They then select one card to put on the bottom of one of the piles, i.e. the pile from which they take a card need not be the same as the one that they discard to. Any pile must not contain more than P cards. Note that at any time a player can have at most P+1=5 and no fewer than P=4 cards in their hand.

When a player holds P=4 cards which are all of the same kind (i.e. four Aces) they declare a win and participate no further in the game. The game continues until all players have declared a `win'; then the game ends. The `winner' of the game is deemed to be the first player to have claimed a `win'; if further players claim a `win' without having picked up a card, it is deemed to be tied between them.

The game can be played with other configurations, as follows:
P players C kinds of card P'piles n cards placed on a pile
2 3 1 2
2 3 2 1
3 4 3 1
4 6 4 2

In order to model the game, the different kinds of cards may be represented as integers in the range 1..C. A value of 0 may be used to denote an empty slot in a pile. There is no need to model the suites; cards of the same suite simply have the same value.

The dealer and all players are deemed to participate in the start action, and all players are deemed to participate in the end action. To facilitate deadlock analysis by the LTSA tool, they should engage in an endless series of end actions. In all other actions, only the 2 entities directly involved are deemed to participate.

System Description

Simple system. This is for the simple case of the game P=2, C=3, P'=1, n=2.

Intermediate system (part 1). This is to implement the case P=2, C=3, P'=2, n=1 for the (FSP) model, but all cases for the Java implementation.

Intermediate system (part 2). An important progress property for this game is that there is always one pile that is not full (whenever a player wants to place a card) and one pile that is not empty (whenever a player wants to pick a card) (so that any player can perform their next action). Specify such a property in FSP and a composition of your game model with this property (it is expected that this composition will be free of deadlock). In your implementation, for P≥3, a smart strategy should be implemented, where the player always keeps the cards with the highest number of other cards of the same value in the current hand. When the smart strategy option is activated, the player of the lowest id (and no others) should use this strategy.

Extended System This game is inherently unfair. A player can be starved of pick actions by other players who keep beating them to the piles. Specify an FSP process FAIRPLAY that prevents any player from performing more than F>0 pick actions than from any other player (who is still playing). Specify an FSP progress property together with an composition with appropriate action priority to check this (for at least one of the players). You will probably find the LTSA tool still detects a progress violation; in a comment in your FSP code, explain how the game rules / model would have to be changed for the LTSA to be able to detect that fairness is being enforced. In your implementation, activate enforcement of fairness when F>0.

Requirements

You submission must include the following: Lines in all 3 files should be formatted to a standard width of 80 characters. Your FSP and Java files should follow good programming style conventions. In particular neat and consistent code layout and adequate commenting in both are important. Your FSP compositions corresponding to each stage should pass the default Safety checks.

Your solution may attempt any of the three levels of the system; please only submit for marking the code for the highest level. Note that for the intermediate and advanced levels, CardGame.java should also be able to handle the simple case P = 2, P'=1, n=2.

Marks will be allocated to the system levels approximately as follows:
System COMP2310 COMP6310
Simple 60 50
Intermediate I 80 70
Intermediate II 100 85
Extended 100 100
The FSP and Java code do not have to be at the same level (in which case this should be explained in ReadMe.txt); there will be approximate weighting of 1/3 for the FSP and 2/3 for the Java, except for the Extended System (where they will be 50% each). A model/implementation at a particular level with serious flaws/bugs cannot score better than one at the next lower level.

CardGame Parameter and Event Classes and Applet Version

The CardGameParam class will provide some ways of controlling the simulation. You can adjust these values in the shell which you run your program from, e.g. for the Bash shell: This will enable repeatability in random number generation between runs, which may be helpful when debugging To return to default behavior: in which case, the random seed will be time dependent. Another environment variable used by this class is $CardGameMaxEvent (this will terminate execution after this number times P2 events are recorded). The interface for the CardGameParam class is:
public CardGameParam(String[] args); // args as from main(String[] args)
int  getP();          // returns number of players 
int  getPprime();     // returns number of piles
int  getN();          // returns number of cards initially on a pile
int  getF();          // returns the fairness parameter
bool isSmartPlayer(); // returns if -S was specified in args
long getGameSeed();   // returns a random seed for the game
int  getRandVal(int max); // returns a random number in 0..max-1
int  getC();          // returns the number of kinds of cards
The `interface' for the class CardGameEvent class is as follows:
CardGameEvent(CardGameParam cardParam); 
// log respective game actions + their parameters in a consistent format    
void logDeal(int playerId, int cardId);
void logPlace(int pileId, int cardId);
void logPick(int playerId, int pileId, int cardId);
void logPut(int playerId, int pileId, int cardId);
void logWin(int playerId);
void logStart();
void logEnd();
void logOtherEvent(String eventDescription);
// sleep for some random time in 0..SleepFactor-1 ms
void sleepEvents();

Hints