Concurrent and Distributed Programming (PCD)

Josep Carmona

This page contains the lab classes for the PCD course. There are 7 sessions for the whole semester,
that will be given every two weeks. The workload expected by every student for each session is:
The purpose of the lab classes is to provide the necessary knowledge to understand concurrent and distributed
programming in two main programming paradigms: imperative and functional. For the former, we will present
Java as the language for concurrent imperative programming. For the later, we will devote two sessions to
understand concurrent functional programming in Erlang. Finally, a session on Petri nets modeling and analysis
will be done.

The following is the schedule of the sessions:


Concurrent and Distributed Programming in Java

Session 0: Java basics
Before the session:
  1. Read the Java tutorial . Make sure that concepts like class, inheritance, interfaces are understood. A tutorial in Catalan (made by X. Messeguer) can be found in this link.
  2. Try the "Hello World" example in your machine.
During the session:
  1. Make a Java program that writes the factorial of a number introduced by the user.
  2. Make a Java program that sorts a vector using the Quicksort method presented in the following paper (the one presented as "Program 4").
  3. Make a Java program that sorts a vector of rationals using the previous method.
  4. Make a module for a Binary Search Tree (BST) with the following operations: create_empty(), is_empty?(a), insert(a,x),inord_traverse(a).
After the session:
  • Make a Java program that, given a sequence of rationals: 1) Inserts the sequence into a BST, and 2) traverses the BST in inorder. What is the outcome ?


Session 1: Java Threads
Before the session:
  1. Read the JAVA tutorial on Concurrency. Make sure that the following concepts are understood:
    • Thread, Runnable interface,
    • sleep()/start()/run() methods,
    • Synchronized code/methods
    • Guarded blocks (monitors)
A tutorial in Catalan on these concepts (made by X. Messeguer) can be found in this link.
  1. Compile and run some of the examples provided in the tutorial.
During the session:
  1. Make a JAVA program to model a Producers/Consumers system. There should be a stack which is filled by Producers and emptied by consumers. Use the class stack from JAVA, with MAX elements. The producers can fill elements while the stack is not full, whilst the consumers can take elements whilst it is not empty. Visualize the contents of the stack while executing the program. For simplicity, consider only one producer and one consumer at the beginning.
  1. Make three JAVA programs (one for each condition below) with four processes which write letters from the alphabet {a,b,c,d} 100 times, under the following conditions:
    1. Without requiring any specific order, i.e., without guarded blocks.
    2. Writing abcdabcd...
    3. Letters a and d must be intercalated as letters b and c, but each pair independently, as in the word adabdadcb.
Make the programs in such a way that it can be easily generalized (adding a few lines of code) to 10 instead of 4 letters.
After the session:
  • Make JAVA programs that are modifications of the program 1 done during the session (Each one of the modifications must be done starting from the initial version of the program (i.e., don't do them incrementally!)):
    1. Producers produce different amount of elements, Consumers consume different amount of elements.
    2. Producers produce different types of elements, and Consumers consume also different types of elements. Then a consumer must wait until a producer of its type has generated the item he is waiting for.
    3. Producer-Consumer nodes: there are some nodes that have both roles (producer and consumer), and when they cannot consume go to produce few items and try to consume afterwards.
  • [OPTIONAL] : Adapt the BST class presented in the previous session to allow for concurrent insertions, by using synchronized methods. Make a program where several threads insert concurrently in a BST and provide the contents at each insertion.



Session 2: FSP, LTS and JAVA
Before the session:
During the session:
  • Implement the problem 1.5 (Token Ring) in JAVA. In the implementation, make sure that the program can be generalized to rings of more than three processes.
  • Implement the problem 1.7 (Town Council Office) in JAVA. IMPORTANT: consider only one worker and one client. The client arrives and after doing his/her duty, sleeps and tries again.
After the session:
  • For the example 1.7 done before, consider the following extensions:
    • N clients, 1 worker
    • N clients, M workers, with N,M > 1.
    • Consider two types of requests, which have two types of services (e.g. asking for a marriage certificate will require the service to produce it, whilst asking for a fine exemption will require a different service).
  • [OPTIONAL] Implement the problem 1.23 (Shopping at ebay.com) in JAVA.


Session 3: FSP, LTS and JAVA: the 50 prisoners problem and variations
Before the session:
  • Solve the 50 prisoners problem in FSP. Try them with the LTSA tool. An initial implementation in JAVA for only three prisoners and can be obtained here (by K. Gabarró), but we strongly encourage you to do it yourself from the scratch without looking at the solution. Here you can find the FSP for three prisioners and with the initial state of the light known.
During the session:
  • Implement the 50 prisoners original problem in JAVA.
  • Consider the following variation of the 50 prisoners original problem: at the beginning, the prisoners are divided into groups which always enter into the room together. Therefore a switch is not enough when a group of size greater than one enters into the room (a counter is instead more appropriate).
    • Model the new scenario in FSP.
    • Implement the system in JAVA.
After the session:
  • Consider the following variation of the 50 prisoners original problem: the initial state of the light is not known (it can be either on or off). In this situation, one can realize that counting twice each prisoner will be enough no matter which is the initial state of the light (see this document where the solution is explained, created by R. De Nicola).
    • Model the new scenario in FSP.
    • Implement the system in JAVA.


Concurrent and Distributed Programming in Erlang

Session 4: Concurrency in Erlang: basics
(Students from ERASMUS MUNDUS also attending the SODX course: skip this session and do instead Session 5)
Before the session:
  1. Read the following Erlang tutorial (specially the first sections until "Functionally Solving Problems", but feel free to complete the tutorial). Try yourself to install Erlang and compile simple programs on your machine.
  2. Read the two sections on concurrency in the Erlang tutorial. Make sure concepts like spawn, pid, !, and receive ... end are understood.
  3. Follow this tutorial (by J. Montelius) which contains simple examples of what you have learned in the previous step.
During the session:
After the session:
  • Solve in Erlang the following problem.
  • [OPTIONAL] Extend the program to allow for having both normal and "special" clients". Special clients can ask to disconnect some other client.


Session 5: an Auction system

Before the session:
  • Learn the concept of auction. Think how to apply this concept in the context of Erlang processes.
During the session:
  • Make an Erlang distributed program for an auction. There are two types of processes:
    • Agent: the process that manages the auction. Its duties are: start the auction, receive the bids from the bidders, finalize the auction (after a certain number of seconds), announce the winner. There should be only one process agent. The policy for the auction considers the following rules:
      • Each time a bidder performs a bid to the agent, its bid substitutes the previous bid (if any). 
      • The bid starts with an initial value decided by the agent. Bids which are less than this value are ignored.
      • Once the auction finishes, if no bids exist, the auction is re-started again with half of the value.
    • Bidder: each bidder receives the bids from other bidders and may perform its bids. At any time, the bidder can leave the auction (its bid will be deleted from the current bids). There is no limit to the number of bidders (even zero).
[HINT: Follow the structure of the program in the previous session.]
 
After the session:
  • Provide the code of the program.

Session 5bis (only for students from ERASMUS MUNDUS also attending the SODX course): Primes!

Before the session:
During the session:
After the session:
  • Provide the code of the program.


Modeling and Analysis with Petri Nets

Session 6: Petri nets

Before the session:
  • WoPeD is a very simple and intuitive tool for the modeling and analysis with Petri nets. Download and execute this tool in your platform.
  • In Help -> Sample nets you will find several examples of Petri nets. Among them, try some of the following: Ballgame, Mailbox, MailboxBounded, MailboxUnbounded, TwoTrafficLightsSafeFair and VendingMachine. For each one of these examples, try to understand them by simulating some execution (Button "Start tokengame").
During the session:
  In this session you will learn how to create Petri nets from the scratch using the WoPeD editor and how to analyze them.
  • The first part of the session is an interactive presentation of the WoPeD editor and its analysis capabilities for a very simple example. Be sure that concepts like Boundedness, Liveness and Reachability Graph analysis are well understood and that you are able to apply them within the tool.
  • The second part of the session is driven by small modeling and analysis exercises: from the "Concurrent Programming Problems" list by J. Castro, try some of the ones that regard Petri nets (e.g., 1.14,1.20,1.27).
After the session:
  • Use WoPeD to model and analyze the production cell system that can be found in page 14 (Fig. 3) of the following paper. At the beginning of page 14 there is a short paragraph explaining the system (you don't have to read anything else of the paper).
  • Provide a report explaining: the modeling of the system within WoPeD (figure of the system), and its analysis (determine using WoPeD whether the system is bound/live and the size of its reachability graph).