Enlarging letters   Home   Information   Contacting   Map
Catalā   Castellano

Concurrent and Distributed Programming (PCD)

Credits Dept. Type Requirements
7.5 (6.0 ECTS) LSI
  • Elective for DIE
  • Elective for DCSFW
  • Elective for DCSYS
 PRED - Prerequisite for DIE , DCSYS
PS - Prerequisite for DCSFW

Instructors

Person in charge:  Xavier Messeguer Peypoch (peypoch@lsi.upc.edu)
Others:Jorge Castro Rabal (castro@lsi.upc.edu)

General goals

The aim of this subject is for students to learn to design and implement concurrent and distributed programmes securely and reliably. To guide the students in the design process, they are introduced to LST (Labelled System Analyser), a simple programming language that allows one to design, visualise and analyse systems of transitions. In order for them to have a broader idea of concurrence and distributed systems, students are taught other models, such as Petri networks and the software designed for analysing them. In order for students to gain a complete understanding of the steps of the process, from modelling to implementation, they undertake practicals in Java programming.

Specific goals

Knowledges

  1. Learn the use of transitional labelling systems as a design tool and for analysing concurrent and distributed programmes.
  2. Learn a software package, e.g. LTS, for the design and analysis of transition systems.
  3. Learn Petri networks and other formal models for design and analysis, and some specific analysis software.
  4. Acquire a clear idea of the basic problems that can arise in concurrent and distributed programming.
  5. Learn parts of Java related to concurrent and distributed programming.

Abilities

  1. Ability to model and analyze simple examples of concurrent programmes through the use of label transition systems.
  2. Ability to use an analytical tool based on transition systems (LTS, for example).
  3. Learn Petri networks and other formal models for design and analysis, and some specific analysis software for Petri Networks.
  4. Ability to use parts of Java related to concurrent and distributed programming.

Competences

  1. Ability to formally argue whether or not a design is correct, using programmes for this purpose where necessary.



    .
  2. Ability to pass abstract tools for design and analysis, and for implementation in programming languages (Java, for example).

Contents

Estimated time (hours):

T P L Alt Ext. L Stu A. time
Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Transition systems and process algebra.
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 8,0 0 20,0
Transition systems and primitive processes. Prefixing and selection operations. Concurrent processes and their execution. Description of LTS systems. Implementation en Java.

2. Concurrent objects, mutual exclusion, synchronisation conditions, deadlock.
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Problem of destructive interference. Locks and mutual exclusion. Semaphore modelling and the problem of nested monitors. Deadlock, analysis using LST.

3. Safety and liveness.
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Description and examples of safety and implementation through LTS. Description of liveness, particularly in connection with progress and implementation in LTS.

4. Passing messages and client/server architecture, other architectures.
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 8,0 0 20,0
Passing synchronous and asynchronous messages. Rendez-vous and client server architecture employing LTS.



Introduction to other architectures: filter pipelines, supervisor/workers, advertiser/recipient.

5. Petri networks, model and basic algorithms.
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Examples of Petri networks. Karp and Miller algorithm.



Special classes of Petri networks. Software tools for analyzing these networks.

6. Petri networks; modelling.
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Case studies: "distributed rearrangement", self-stabilising mutual exclusion, protocols with acknowledgment (ACK) messages.

7. Algorithms in networks
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 2,0 0 2,0 8,0 0 20,0
Choice of leader, echo algorithm, mutual exclusion in network, consensus, non-directed trees, self-stabilisation.


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
28,0 28,0 14,0 0 14,0 60,0 0 144,0
Avaluation additional hours 6,0
Total work hours for student 150,0

Docent Methodolgy

Examples will be used to introduce basic concepts in the theory classes. Students will solve exercises on theory class themes in the practical classes. Lab classes will cover implementation of these problems (or similar problems) in Java. Both the lab and problem classes may employ design and analysis tools such as LTS.

Evaluation Methodgy

There will be a final exam and a lab grade. The exam will comprise problems on the theory taught. The lab grade will reflect the quality of students" work. The final grade will be calculated as follows:



final exam*0.7 + lab grade*0.3

Basic Bibliography

  • Magee, Jeff Cramer, Jeff Concurrency, state models & Java programs, Wiley, 1999.
  • Reisig, Wolfgang Elements of distributed algorithms, modeling and analysis with Petri nets, Springer, 1988.
  • Perterson, James Petri net theory and the modeling of systems, Prentice-Hall, 1981.
  • Tomás, José i d'altres Programaciķn concurrente, Thomson, 2003.
  • Tel, G. Introduction to distributed algorithms, Cambridge, 1994.

Complementary Bibliography

  • Lea, Doug Concurrent programming in Java (hi ha traducciķ al castellā), Addison Wesley, 1999.
  • Lewis, Bill, Berg, Daniel Multithreading programming with Java (existeix traducciķ al castellā), Prentica-Hall , 2000.

Web links

  1. Obrir nova finestra http://www-dse.doc.ic.ac.uk/concurrency/


  2. Obrir nova finestra http://java.sun.com/


Previous capacities

Sound knowledge of Java regarding classes and objects.



 
logo FIB © Barcelona school of informatics - webmaster@fib.upc.edu - RSS RSS