Distributed systems  						26.2.2004

Exercise 1

No X-exercises this week.

Read the questions carefully, answer to all parts of each question. Draw
a picture of each exercise.

1) Design a manual message-passing sorting algorithm for a set of
   persons and A4 papers. Each paper has a name according to which it is
   sorted. At the beginning, all papers are in a stack by the first
   person.  At the end, the sorted papers should be returned to the
   first person. A person can perform local operations and give a stack
   of one or more papers for the neighboring person. The recipient needs
   not to be ready to accept the stack (post-pox messaging). No person
   can move from his/hers position. You can assume that the names are
   uniformly distributed within the alphabet.

   Assume that you have a) 10 persons, b) 100 persons located in a single row.
   Assume that you have A) 100 papers, B) 10000 papers.

   Design the sorting algorithm (as fast as possible) to do the
   real-world sorting (in both a and b sitting arrangements and both A
   and B paper piles.). Estimate the time needed (in seconds) for all
   (Aa, Ab, Ba, Bb) cases.

2) Modify the previous case b) algorithm so that instead of a single
   row, the persons are located in a 10 by 10 matrix, and are able to
   pass the papers in 4 directions. Take advantage of the reduced
   diameter of the human network. Estimate the time again for both A and
   B cases.

3) Define a protocol for agreeing a dinner time for N (e.g., 5) persons
   using (GSM) SMS messages. Try to keep the total number of messages at
   minimum. You can assume that all of you know each other's GSM numbers
   and have a (logical) linear (or circular) order. Do not assume that
   your only suggestion succeeds. Instead, assume constraints from every
   participant.

We shall design a peer-to-peer (no centralized server) chat system using
asynchronous communication. Assume that you have primitives send(out
address, out message) and receive_from_any(in address, in message). The
address is, e.g., a mobile phone number or IP address, the message is a
free form text field. A person can connect to an existing chat group by
sending a join message to an existing user or start a new group. Any
user may write a line of text, which is then relayed to all joined users
by the system.

4) Design the protocol (messages, relaying) of such system. Consider
   also a case when a user quits the system and a case when a message is
   lost. To keep the solution and communication costs reasonable, the
   system does not have to be 100 % reliable.

5) Outline a system for global person ID numbers. In this system each
   newborn person in the Earth is given a unique ID as soon as possible
   (in that case, considering the local and personal differences). In
   addition to giving the IDs, the system should be able to store some
   information of each person, and to be able to tell whether a given ID
   has been assigned or not. There would be billions (109) IDs and
   millions of users of this system worldwide. Sketch the protocol and
   information infrastructure for assigning the IDs, modifying the
   information, collecting, and distributing information to all users.