Distributed Systems, Spring 2007

Home exercise 3

The essay should be returned by e-mail to 
Lea.Kutvonen@cs.helsinki.fi, mika.karlstedt@cs.helsinki.fi 
as an attached file (preferably in pdf format, with the name 
[last name].[format type]) at the latest on Monday 19.2. at 23.59.
       
1. The "two-army problem" and the "Byzantine generals problem" are examples
   of how difficult it is to reach agreement in faulty systems.
   a) What kinds of failure behavior are treated in these examples?
   b) Is it possible to make these types of failure-prone systems fault-
      tolerant through replication? If it is not then explain why not
      (shortly!). If it is possible, then describe the algorithm's basic
      ideas and explain why it works (shortly!).
   c) How is the two-phase commit in transaction processing related with
      these problems?
   (In the lecture material the "two-army problem" was described using an
    example, where Alice and Bob tried to agree upon a common lunch invLa    Tryste.)

2.  The components of a distributed system communicate using message passing.
    To improve the fault tolerance of an application certain components have
    been replicated. However, the correctness of the application is based on
    the assumption that all components receive all messages in the same order.
    a) Describe the algorithm (included in the message passing system) which
       implements this ordering requirement. The algorithm must be fully
       distributed and symmetric (in the sense that all nodes use the same
       algorithm).
    b) Justify the correctness of your algorithm. What does your algorithm
       assume about the characteristics of the underlying data communication
       system? (It is advisable to base your eplanation on an appropriate
       example.)