Saltar al contingut Menu
Map
  • Home
  • Information
  • Contact
  • Map

Concurrent and Distributed Programming (PCD)

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

Instructors

Person in charge:  (-)
Others:(-)

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 model 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 Nets. In order for students to gain a complete understanding of the steps of the process, from modelling to implementation, they undertake practicals in Java and Erlang programming languages. To model Petri Nets we use WoPeD.

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.
  4. Acquire a clear idea of the basic problems that can arise in concurrent and distributed programming.
  5. Learn parts of Java and Erlang 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 as another formal models to design and analysis.
  4. Ability to use parts of Java and Erlang 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 as Java and Erlang.

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 
6,0 6,0 3,0 0 3,0 12,0 0 30,0
Transition systems and primitive processes. Prefix and Choice operators. Concurrent processes and their execution. Description of LTS systems. Implementation in Java and Erlang.

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 
6,0 6,0 3,0 0 3,0 12,0 0 30,0
Message passing. Client/server architecture
Introduction to other architectures: filter pipelines, supervisor/workers, advertiser/recipient.
Message Passing in Erlang. Client/server architecture in Erlang.

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.
Introduction to WoPed.



Special classes of Petri 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.


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 and Erlang. 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:
0.6*final exam + 0.4*lab grade

Basic Bibliography

  • Jeff Magee & Jeff Kramer Concurrency : State Models & Java Programming (Second Edition), John Wiley & Sons, 2006.
  • Perterson, James Petri net theory and the modeling of systems, Prentice-Hall, 1981.
  • José Tomás Palma Méndez ... [et al.] Programación concurrente, International Thomson, 2003.
  • Joe Amstrong Programming Erlang, Software for a Concurrent World, Pragmatic Bookshelf, 2007.
  • Sharon Zakhour, Scott Hommel, Jacob Royal, Isaac Rabinovitch, Tom Risser, Mark Hoeber The Java Tutorial, Fouth Edition, a Short Course on the Basics, Addison Wesley, 2006.

Complementary Bibliography

  • Doug Lea Concurrent programming in Java (Second Edition) : Design Principles and Patterns, Addison-Wesley, 2000.
  • Bil Lewis, Daniel J. Berg Multithreaded programming with Java technology, Prentice Hall, 2000.
  • Francesco Cesarini, Simon Thompson Erlang, a Concurrent Approach to Software Development, O' Reilly, 2009.

Web links

  1. http://java.sun.com/


  2. http://www.doc.ic.ac.uk/~jnm/book/


Previous capacities

Sound knowledge of Java regarding classes and objects.


Compartir
Share

 
logo FIB © Barcelona school of informatics - Contact - RSS
This website uses cookies to offer you the best experience and service. If you continue browsing, it is understood that you accept our cookies policy.
Classic version Mobile version