Distributed System Implementation, Spring 2000

(Hajautettujen järjestelmien toteutus, Kevät 2000)



I am extending the deadline until  15.6.
We stick to the problem definition available given below.
If you need some help, e-mail me (jyrki@cs.uta.fi).
Contact me by 12.6. at the latest about handing in your coursework.

LECTURES: The lectures are finished.

EXERCISES: The exercises are finished.

LECTURE MATERIAL: I have handed out lecture notes 1-7, and
they form the core of the contents for the course (and the exam).
I have photocopies on concurrent system theory and a (partly Finnish)
collection of seminar papers on various issues, like Corba.
I will put some copies in the bookshelf opposite to room 3082.

EXAMINATION: The examination will be on 25.5. at the public
CS examination time and place.

JDK IN THE MAIN CS COMPUTER LAB: The paths are not set,
so you need to set them yourself - as in the JDK.BAT file given
somewhere in the java startup material. Without this, you may not
be able to access the cryptographic package. If you have further problems,
e-mail me.

yet done it...


General information



Literature - Kirjallisuutta

Get started with java  and  sockets

Get started with Java RMI and Corba

Check out the distributed commit simulation applet!


General information

As some foreign students have already  expressed
their wish to follow course, the teaching will
be given in English.

The practical arrangements are explained in more detail
in the first lecture note, which is handed out on the first lecture,
but I will explain a little something right here below.

In principle, this is a fairly traditional course. There are lectures,
weekly exercises, and courseworks (probably two).
However, the pattern is slightly modernised.

Usually, I have something I want to show or explain. For that,
there will be traditional lecturing with software demonstrations.

You should learn by doing, however. That is why there will be weekly exercises.
I will try to give the exercises on Wednesdays and you
will have to do them by the following Wednesday. This way, you can ask
about them on Tuesdays, if there are some problems about the exercises.
There are no separate exercise groups or sessions - we will do them
at the start of the Wednesday sessions.

The course will include a coursework with two parts. One is a fairly
practical application. At the time of writing this, my idea is that
you will get parts of the application from weekly exercises.
The other part will be a more theoretical part.

A little note: The RMI examples do not seem to work
on jdk1.1.6 (and Corba examples definately do not,
if you only have jdk1.1.6 - it is possible to do Corba with
that as well if you install some extra software, though).

I have no motivation to try to fight with jdk1.1.6. so
in my point of view the only reasonable thing to do
is to move on to Java 2 (jdk1.2.2).

The Computer Science main computer lab has Java 2
(jdk1.2.2), so you can use that for the RMI. It will
have idltojava compiler as well, so in the near future
you can use it for the Corba examples as well.
I talked to the Computing Centre about this, and they seem
to be willing to upgrade as well.



I have put leftover copies of the notes in the bookshelf opposite to room 3082
(not far from my office).

A correction to note 3, page 4: In the definition for causality violation it
should say "but r(m2)  <p  r(m1)".

Here's a copy of the powerpoint lectures on distributed system risks.

Here's a copy of the powerpoint lectures on keys, encrypting, and authentication.

Here's a directory containing the cryptographic examples we have used in the lectures
(they will mostly be from the textbooks).

This is a link to the www.cryptix.org website, where you can download their
JCE compatible cryptographic extension, if you want it e.g. for your own computer.
(Sorry, but the www.cryptix.org seems to be really slow, so I can't use them.
You should find the JCE compatible extension from their pages yourself - I will
update these pages in the near future.)

This is a link to some JCE documentation. (Coming up - it is link which can be found
from the Cryptix pages, but I can't reach those pages now.)

This is a link to java security tools documentation.

Exercise information

1. (26.1.) Exercises 1 and 2 from Note 2.

2. (2.2.) Exercises 1-3  from Note 3 (sorry, no hope, exercise 4 will eventually be given).
Solution to Exercise 1.
Solution to Exercise 2.
Alternative solutions to Exercises 1-2.

3. (9.2.) The following exercises:
3.1. Give an example, where we use Lamport's timestamps and for two events e and e' we have
e.TS <e'.TS but we do not have e <H e'. (This should be dead easy).
3.2. Suppose we use vector timestamps and only increment the timestamps on sending of messages
(not on receipts) to keep a track of the messages we have seen and suppose that we try to
implement causal communications without multicast (messages are only sent to the recipient).
Construct an example, where there are three processors sending messages to each other
and all are blocked waiting to see a message from another processor (in other words, the
system deadlocks).
3.3. Examine the possibilites to implement causal communications using Lamport timestamps
and a multicast.

4. (16.2.) The following exercises:
4.1. Implement a mutual exclusion algorithm using RMI.
4.2 Implement a leader election algorithm using RMI.
- There's only two exercises, and therefore you should have time
to do some reading on RMI and really get started with it.
You can read from the web or from Farley's book.
Some solutions here!

5. (1.3) The following exercises:
Exercises 5.1-5.3 are meant to be done with pgp, which is
available on kielo. You can type pgp -h for help.
5.1. Create yourself a private key and a public key.
5.2. Encrypt a document with yourself as the recipient, and then decrypt it.
5.3. Exchange public keys with a friend. Then both encrypt and sign a document
for the other. Exchange documents and decrypt them.
- The self-study exercise is coming up. Follow this space.

6. (8.3.) The following:
6.1. Suppose locks are taken implicitly as data items are used, and unlocking happens
explicitly. Consider the schedule; (look up the notes if you need help with the notation).
r 1[x]->w1[x]->unlock1[x]->r2[y]->r2[x]->w2[y]->unlock2[y]->unlock2[x]->r1[x]->unlock1[x]->c1->c2.
a) Is this according to 2PL?
b)  Is the schedule of conflict-serializable? If it is, show it. If not, find a
conflict serializable schedule.
6.2. How many serial and how many conflict-serializable schedules are
there for the transactions of schedule 6.1?
6.3. Implement yourself a 2-phase commit using either sockets or RMI.

7. (22.3.).
7.1 Give an example where blocking happens in the case where
a) eventually  the decision will be abort (some site has voted to abort), and
b) eventually the decision will be commit (all sites have voted to commit).
7.2.  In 3PC time-out will imply a re-election of the coordinator.
Would it be beneficial to re-elect a coordinator in 2PC at a time-out?
7.3 Suppose we use uncoordinated checkpointing. Explain how
garbage collecting old checkpoints can be done (ie. when can we
throw away an old checkpoint?).

8. (29.3.).
8.1 Consider the example of TIP in the powerpoint slides
on distributed system risks. (The example with User's Web Browser etc.)
Write down the sequence of TIP commands related to the transaction.
8.2. Find out more ways (in addition to the ones in the note) to do denial
of service attacks with TIP.

5.4.: There are no exercises for 5.4. It feels likely that the main subject for 4.4. and 5.4.
is going to be cryptography. It might be a good idea to use the time towards
the coursework.

9. (12.4.).
9.1 Write a non-distributed implementation of data manager A
(as in the coursework).
In your implementation you may, for instance, give the commands
using a keyboard instead of using messages.
9.2. Change your implementation of data manager A in
such a way that the data manager discusses with a distributed
process (e.g. using sockets or RMI).

10. (19.4.)
10.1. Extend the StrongClient - StrongServer application (you may also
create an RMI version of it, if you wish) so that at login, either party
sends a byte array for secret key generation (as in SafeTalk), and after the initation
the client sends to the server something which is encrypted using a cipher
initiated with that key and the server decrypts it.
10.2. Exercise 9.2. with secure communication.


- Chow & Johnson: Distributed Operating Systems & Algorithms, Addison-Wesley.
- Farley: JAVA Distributed Computing, O'Reilly & Associates.
- Knudsen: JAVA Cryptography, O'Reilly & Associates.
- Magee & Kramer: State Models & Java Programs, John Wiley & Sons.
- Orfali & Harkey: Client/Server Programming with JAVA and CORBA, John Wiley & Sons.



This is a preliminary suggestion for the coursework.
It is still under discussion. If you want to implement
it not as just a set of Java programs but, say, using
Corba, please contact me.


Implement a system with the following properties:


Two data managers data_A and data_B, both of which manage an array
[0,..,maxInd] integers (A and B, respectively). The integers are
meant to be non-negative. The initial values can be chosen randomly
from the range [0,maxValue] or read from an input file, whichever.
For simplicity, we call the arrays A and B, respectively.
The data managers give following services (only):
0. Initiate a transaction t for user X (return a transaction id).
1. Lock data item T[i] for transaction t.
  (Only possible if there is no lock on i.)
2. Read value v to T[i] for transaction t.
3. Write T[i] for transaction t.
4. Commit a transaction t.
5. Roll back a transaction t.
If you want more excitement out of this, you
may also implement unlock operations.
Otherwise all data items are unlocked at
commit or rollback. We are not so much interested
in the recovery of a crashed data manager, so you
may implement your program so that it only keeps
data in main memory at run time.


Two servers server_A and server_B, which give the following
kinds of services
- serve clients requests by calling the data managers
- server_A handles data only on data_A and server_B only on data_B
- only server such requests that the values remain positive
- there may be many servers (processes or threads)


Client processes, which, when started, do the following.
1. Log on and start a transaction on server_A and server_B.
2. As long as the user wants, repeat
2a. Choose randomly or ask the user for 2 indices i and j,
  0 <= i <= maxInd, 0 <= j <= maxInd
and a value v, -maxValue <= v <= maxValue.
2b. Request v to be added to A[i] and subtracted v from B[j].
3. Log out and finish the transaction.
- The clients may also perform other operations to solve
problematic situations.


- There is only one type of lock (exclusive).
- Servers need some user management, preferably with public/private key pairs.
- Cipher the communication.
- The system should be implemented in a way which allows all the
processes to be executed on different computers (or all on the same
computer, alternatively).

30.3.2000 JN