Approximate translation of the October 24 2006 exam in Distributed Systems
Use the original Swedish exam for figures and tables.

Total score: 60 points
Grade 3/4/5: 30/39/48 points
No tools or other aids are allowed.

Assignment 1:
In designing distributed systems, one can use different types of models. Two such models are architectural and fundamental models:
  a) What is the purpose of an architectural model
  b) Name one architectural model and give a short description of it
  c) What is the purpose of a fundamental model
  d) Name one fundamental model and give a short description of it

Assignment 2:
As one analyzes or designs a distributed system that uses a middleware, there are a few questions one should keep in mind. Among these, one should consider how processes can exchange data in a heterogeneous environment (regarding e.g. networks, hardware, and software), and how to handle errors in a distributed environment.
  a) What is a middleware?
  b) State two reasons as to why one would like to use a middleware.
  c) Discuss why one should consider how processes exchange data in a heterogeneous environment, and how one may handle problems that arise in this situation (give two examples).
  d) Discuss why one should consider error handling in a distributed environment, and how one may handle errors that arise in this situation (give two examples).

Assignment 3:
In distributed systems, it is non-trivial to ensure that all processes have the same clock values. Two reasons for this is that software clocks are incorrect and that synchronizing clocks over a network is hard.
  a) Why do software clocks become incorrect over time?
  b) Describe the Berkley algorithm for synchronizing clocks over a network and state whether it is used for internal or external synchronization.

In many distributed systems the precise time for some event is not as important as the ordering of events. In such systems one can use the happened-before (HB) relation and logical or vector clocks instead of time values.
  c) What is the happened-before relationship (give definition)?
  d) What are logical clocks and how do they work (show an example)?
  e) What are vector clocks and how do they work (show an example)?

Assignment 4:
Consider Ricart and Agrawala's algorithm (look at the Swedish exam, guys!) that is used for gaining access to a critical section where only one process may be at a time. Assume that the system where the algorithm is used is asynchronous, that processes do not crash, and that messages are sent reliably.
  a) What three requirements do we have on general algorithms for gaining access to a critical section? Name and define these three requirements.
  b) To make Ricart and Agrawala's algorithm work we need all processes to agree on which order they may enter the critical section. Logical clocks are used in the algorithm, but this is not enough to enable the processes to agree on the order. How would you solve this problem?
  c) It is common in many systems that a process that enters the critical section wishes to return to the critical section many times before some other process requests access. Explain why Ricart and Agrawala's algorithm is inefficient in this case and suggest a modification to the algorithm that improves performance in this regard.

Assignment 5:
Explain the difference between sequential consistency and linearizability, and why the former is more practical from an implementation point of view.

Assignment 6:
  a) Describe how optimistic concurrency control works.
  b) In what situations may optimistic concurrency control be a better choice than locks?

The transactions T and U in a server are defined as follows:
	T: (T1) x = read(i); (T2) write(j, 40);
	U: (U1) write(i, 50); (U2) write(j, 60);
Initially, i=10 and j=20. Assume that the transactions T and U are active at the same time and that optimistic concurrency control is used. State and explain the result for each of the following cases:

  c) T's request to commit arrives first and backward validation is used.
  d) U's request to commit arrives first and backward validation is used.
  e) T's request to commit arrives first and forward validation is used.
  f) U's request to commit arrives first and forward validation is used.

Assignment 7:
In security, the following terms are common topics:
  * Threat analysis
  * Security policy
  * Implementation
  * Maintenance

  a) Briefly explain each of the topics.
  b) Briefly explain how the concepts in the topics affect each other.
  c) Explain why one may correctly state that security is all about risk management.

Assignment 8:
SSL is comprised of four protocols. List them and briefly explain what tasks they perform.

Assignment 9:
Given the following security levels, ordered as follows:
	Top Secret (KH)
	Secret (H)
	Non-classified (P)
where TS is the highest level of security and P is the lowest, and the following categories:
	Marinen {M}
	Flygvapnet {FV}
	Armén {A}

[Mentally insert the two tables here, guys!]

Determine if the following six statements are true or false for the subjects (subjekt in Swedish) and objects (object in Swedish) in the tables:

                  
  a) Andersson 1234 dom Försvarsstrategier
  b) Jonsson 2345 dom Försvarsstrategier
  c) Andersson 1234 dom Marinens organisationsstruktur
  d) Lundberg 3456 dom Telesystem
  e) Johansson 4567 dom Stomnät
  f) Jonsson 2345 dom Arméns organisationsstruktur

Follow-up question:
  g) In this assignment, you have access to information about the security levels, categories, and classifications. What is then the classification for _this_ information? Back up your response with sound reasoning.