Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Concurrent and Distributed Programming (CDP, 213530)
[go: Go Back, main page]

Concurrent and Distributed Programming (CDP, 213530)

The aim of the Concurrent and Distributed Programming course is to study the theory and practice of concurrent and distributed programming. The student will acquire the skills necessary to succeed in a world where almost every aspect of computing is concurrent and/or distributed. The CDP course is a 5 ECTS course intended for 3rd year Computer Science students.

Organisation

Language: The class is taught in English.
Lecturers: Prof Dr Ed Brinksma, Prof Dr Pieter Hartel, and Dr Ir Theo Ruys.
Start: Wed. 26 Aug, 13:45-15:30
Class of 2003/2004 Excel
Book: M. Ben-Ari, Principles of Concurrent and Distributed Programming 1/e, Published April 1990 by Prentice Hall PTR, 225 pp, ISBN: 0-13-711821-X (errata)
Online resources: The book uses Ada, in the course we will use Promela/SPIN instead, the SPIN models from the book are here.
Assesment: Written examination: 70%; Take home assignments 30%
Course information from VIST html

Prerequisites (Mandatory=Verplicht)

  1. Programming I (213500)
  2. Programming II (213505)
  3. Formal Methods for Software Engineering (213520)
  4. Operating Systems (211045)

Objectives

  1. To enable the student to build and to reason about concurrent and distributed applications
  2. To encourage students to use model checking as a standard design tool

Student Outcomes

  1. To be able to understand the fundamental concepts of concurrency
  2. To have built some elementary concurrent and distributed programs
  3. To be able to describe some concurrent and distributed algorithms
  4. To be able to use SPIN model checking tool

Contents

  1. What is Concurrent Programming?
  2. Model checking with SPIN
  3. The Concurrent Programming Abstraction (Interleaving, atomicity, correctness, liveness)
  4. Proving properties of concurrent programs
  5. The Mutual Exclusion Problem (Dekker, Bakery)
  6. Semaphores (invariants, producer consumer, bounded buffers)
  7. Monitors (emulation by semaphores, readers and writers)
  8. Dining Philosophers
  9. Distributed Programming Models (Ada, Occam, Linda, Java)
  10. Distributed mutual exclusion (Ricart-Agrawala)
  11. Distributed termination (Dijkstra-Scholten)

Notes and slides for each week

  1. Aug. 27th Introduction (Pieter)
    Book chapter 1 and sections 2.1-2.3, Slides Power Point
    Modelling (1) (Theo)
    R. Gerth, Concise Promela Reference html , Slides PDF
  2. Sep. 3rd Modelling (2) (Theo)
    Slides PDF
  3. Sep. 10th Proofs (1) (Ed)
    Book sections 2.4-end, chapter 3, Slides Power Point
  4. Sep. 17th Proofs (2) (Ed)
    Book chapter 4, Slides Power Point
  5. Sep. 24th Algorithms (1) (Pieter)
    Book chapter 5, Slides Power Point
    Book chapter 6, Slides Power Point
  6. Oct. 1st Paradigms) (Pieter)
    Book chapter 7, Slides Power Point
    Book chapter 8, Slides Power Point
    Book chapter 9, Homework
    Book chapter 10, Slides Power Point
  7. Oct. 8th No lecture
  8. Oct. 15th Algorithms (2) (Pieter)
    Book chapter 11, Slides Power Point
    Book chapter 12, Slides Power Point
  9. Oct. 22nd Modelling (3) (Theo)
    Slides PDF
    RMI Date Server Example ZIP

Take home assignments

General rules:

Assignment 0: A test (1 out of 30 marks)

Submit your student number, name and preferred email address as a single, plain text file to the handin service. Please do this before lecture 2 (Sep. 3rd)

Assignment 1: Proofs (10 out of 30 marks)

Anwer the following exercises from the book: Note: The characters n and u can be found in Word in the character set Wingdings (character codes 117 and 110, respectively).

Submit your answers as a single pdf file to the handin service, before lecture 6 (Oct. 1st)

Assignment 2: A model (4 out of 30 marks)

Build a Promela model of The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, (See D. Chaum, Journal of Cryptology, 1(1):65-75, 1988).

Three cryptographers are sitting down to dinner at their favorite three-star restaurant. Their waiter informs them that arrangements have been made with the maitre d'hotel for the bill to be paid anonymously. One of the cryptographers might be paying for the dinner, or it might have been NSA (U.S. National Security Agency). The three cryptographers respect each other's right to make an anonymous payment, but they wonder if NSA is paying. They resolve their uncertainty fairly by carrying out the following protocol:

Each cryptographer flips an unbiased coin behind his menu, between him and the cryptographer on his right, so that only the two of them can see the outcome. Each cryptographer then states aloud whether the two coins he can see--the one he flipped and the one his left-hand neighbor flipped--fell on the same side or on different sides. If one of the cryptographers is the payer, he states the opposite of what he sees. An odd number of differences uttered at the table indicates that a cryptographer is paying; an even number indicates that NSA is paying (assuming that the dinner was paid for only once). Yet if a cryptographer is paying, neither of the other two learns anything from the utterances about which cryptographer it is.

Your model should:

Submit your Promela model as a single, plain text file to the handin service, before lecture 7 (Oct. 15th)

Assignment 3: A larger model and Java implementation (15 out of 30 marks)

The assignement is described here PDF. Please gather all files that constitute your answer in a single zip file, and submit the zip file to the handin service, before Midnight Nov 17th.

Examination

  1. 24 Nov, 13:30-17:00 Written Examination (Open book)
    Past exam papers:
  2. 30 Jan 2004, 9:00-12:30 Resit (Written Examination, Open book, Second and last opportunity in academic year 2003/2004)
    Past exam papers: