The course for autumn 2001 will be lectured under the code T-79.231

NEW: The exam for the course Tik-79.231 Parallel and Digital Systems will be held 9 May 2001 at 13-16 at the hall T2 or T1 (further information about the place will be given). The exam will thus be at the same time and in the same place as the exam for the finnish course Tik-79.179. The exam papers will be available in english and in finnish. One more time: There will be _no_ exam for the course Tik-79.231 in 8 May because the exam has been moved to 9 May.

NEW: Exam results, Jan 10, 2001.

NEW: Exam results, Dec 11, 2000.

NEW: Final results for homeworks.

NEW: The next exam will be on Wednesday, Jan 10th 2001, at 9:00-12:00, in the lecture hall T1.

NEW: Demonstration of homeworks on Friday December the 8th at 8.30 in lecture hall T3 (same place where the tutorials were held). I will give information about the correct answers (no model answers will be given, though) and the grading of homeworks.

NEW: The exam is on Dec 11, 2000, at 9:00-12:00 hrs, in the lecture hall T1. The other exams are in January, May, and September.

NEW: What to read for the exam (see below).

NEW: Assistance for homeworks in two wednesdays (22nd nov. and 29th nov.) at 14.15-16.00 in room B345 (near the return box for the home assignments). Note also that the tutorials have ended.

This course is the English version of Tik-79.179 Rinnakkaiset ja hajautetut digitaaliset järjestelmät (3 ov), which will be held in the spring term, 2001. Please note that the courses are similar, if not equal, in content.

Tämä on englanninkielinen versio kurssista Tik-79.179, joka opetusohjelman vastaisesti pidetään vasta kevätlukukaudella 2001. Voit osallistua valintasi mukaan joko englannin- tai suomenkieliseen kurssiin.

Concurrent and distributed systems play a significant role in the implementation of computer based applications. E.g. the Internet, telecommunications protocols, client/server systems, embedded systems, and process control are application domains where an understanding of concurrent or distributed systems and their underlying phenomena are needed. Some of the problems encountered are the issues of timing and synchronization; when solving these problems we benefit from a rigorous approach, formal methods, and efficient software tools.

The goal of the course is to give the student an introduction to the methods and formalisms used in the modelling and analysis of parallel and distributed systems. The lectures cover the theory and use of Petri nets, foundations of temporal logics, and process algebra. To practise modelling and applications of theory there is tutored practical work (laskuharjoitus) and compulsory homework.

Requirements to pass the course:

Examination and compulsory homework (see below).

Lecture time:

Wednesday, 16-19 hrs, room Y405, starting on Sep 20th, 2000.

Exception: No lecture on Oct 18, 2000.

Tutored practise:

Fridays, 8-10 hrs, room T3, starting on Oct 6th, 2000.

Discussion forum:

opinnot.tik.rhj

Literature:

Compendium == lecture slides, to be downloaded from this very page.

• K. Varpaaniemi: PROD Reference Manual

Useful software:

• PROD is an analyser for High Level Petri Nets. There was some trouble with the PROD homepage but it should be OK by now.

Additional material:

• Tadao Murata: Petri Nets: Properties, Analysis and Applications
• Robin Milner: Communication and Concurrency,
• David Walker: Introduction to a Calculus of Communicating Systems.

Lecturer:

Esa Kettunen, M.Sc., phone: 050-380 7284, email: Esa.Kettunen@hut.fi..

Assistant for tutored practise and homework:

Jukka Honkola, phone: 451 5244 email: Jukka.Honkola@hut.fi.

Lecture Slides

• Lecture 1, Sep 20, 2000.
• Lecture 2, Sep 27, 2000.
• Lecture 3, Oct 4, 2000.
• Lecture 3 (minor changes), Oct 4, 2000.
• Lecture 4, Oct 11, 2000.
• (NO LECTURE HELD ON Oct 18, 2000.)
• Lecture 5, Oct 25, 2000.
• Lecture 6, Nov 1, 2000.
• Lecture 7, Nov 8, 2000.
• Lecture 7 with a minor correction in page 8. Thanks are due to Luo Jun Chun for pointing this out.
• Lecture 8, Nov 15, 2000.
• Lecture 9, Nov 22, 2000. (Last lecture.)

What to read for the exam

Home assignments

There will be 5 home assignments, each of which is worth 10 points. One of the requirements to pass the course is to accumulate a total of at least 20 points from the home assignments. If you score 20 to 50 points you will gain extra points in the exam, incrementing your course grade with at most 2.

To be more exact, there will be 5 questions in the exam, each of which is worth 6 points, totalling to a maximum score of 30 points in the exam. To pass the course, 9 points are required (this is a must, you need 9 clean exam points to pass the course; the homework bonuses are calculated after that.)

• 9 to 13 points means your mark for the course is 1.
• 14 to 18 points means your mark for the course is 2.
• 19 to 23 points means your mark for the course is 3.
• 24 to 27 points means your mark for the course is 4.
• 28 or more points means your mark for the course is 5.

In the above calculation of a student's mark for the course, a bonus is added to the exam total according to the following formula: T = E + (H - 20)/3, where T is the total points from the exam and homework, E is the total of points from the exam, and H is the score from the home assignments.

• Homework 1. Deadline: Nov 3, 2000.
• Homework 2. Deadline: Nov 10, 2000.
• Homework 3. Deadline: Nov 17, 2000. (Marko Mäkelä's wise advise follows:) I have been asked how the behaviour of the sender and recipient processes in the 3rd homework could be modeled. The general solution to apply when you do not know the exact behaviour of a subsystem or if the behaviour is too complex to be modeled, is abstraction with non-determinism. Generally, if you don't know the exact outcome of a function (say, x mod 5), you can model it by replacing it with a non-deterministic choice of all values (0, 1, 2, 3, 4 in the case of x mod 5 if you don't know the value of x). Applying non-determinism in the homework is simple: let the sender send all kinds of messages, that is, (sender,recipient) pairs with sender not equal to recipient. The recipient can simply remove the received frames from the ring. I would model the system with three places: a constant place containing all possible messages (which will be read through a bidirectional arc by the sender), a bus place (node,recipient,...) and a place for empty bus slots (containing the node number). You could also use a special recipient number in the "bus" place to denote empty slots (and another value for holes).
• Homework 4. Deadline: Nov 24, 2000.
• Homework 5. Deadline: Dec 1, 2000. Incomplete PROD description to be completed in Homework 5.

Tutorials

Tutorials are special events held by the assistant whereupon certain problems are worked on to give further enlightenment.

The tutorials and their answers will appear here. However, some of the pictures are not in a computer readable form so they will be missing

• Tutorial 1. The dates on the papers are wrong but this is the correct tutorial
• Tutorial 2.
• Tutorial 3.
• Tutorial 4.
• Tutorial 5.
• Tutorial 6.
• Tutorial 7(last tutorial).
• Answers to Tutorial 1.
• Answers to Tutorial 2.
• Answers to Tutorial 3. A picture of the Pr/T-net modeling the Peterson's mutex algorithm is missing. Answer papers with the picture are available outside the room B336 in the Computer Science building. The picture is now available in .eps format
• Answers to Tutorial 4.
• Answers to Tutorial 5.
• Answers to Tutorial 6.
• There are no separate answers for the tutorial 7, everything is in the tutorial paper.