Distributed and Concurrent Systems			7.3.2008
Exercise 1

These first exercises should be done based on common sense and previous
CS knowledge. 1st week lectures are not used. Objective is to seed
thoughts and thinking towards concurrent, parallel, and distributed
systems.

Draw a figure on each question.

1) Design a _manual_ sorting algorithm for a set of persons and a bunch
   of A4 papers (each with a name). At the beginning, there is a stack
   of unsorted papers and the group of people, At the end, the papers
   should be again in one stack sorted. Initially, you have a group of
   10 persons.  Describe the procedure/technique for sorting and estimate
   the time (in seconds, etc.) needed for sorting if the number of
   papers is

   a) 10
   b) 100
   c) 1000
   d) 10000

   Don't use a computer algorithm (such as quick-sort) as humans would
   not really use those (as they are not efficient manually). To
   estimate time, estimate time for each simple operation (such as
   comparing two papers, or moving a paper from a stack to another), and
   multiply by the number of such operations needed in each stage.

2) Continue the previous exercise by refining the algorithm (and time
   estimate) for 100 persons (1000 and 10000 papers) and 1000 persons
   (10000 papers).

3) There are ~6 million mobile phone numbers in Finland, and there are
   about 20 million phone calls made daily. Nowadays, you cannot know the
   correct destination operator according to the destination phone
   number.  Thus, operators need to maintain a database of phone numbers
   and corresponding operators. Further, ~half million numbers are
   transferred to another operator every year. Estimate/sketch what sort
   of system (how larger, how fast) is needed to serve quickly the
   destination operator based on destination number for each phone call.
   Consider also, how the updates on changed operators are made.

4) 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 (10^9) 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.

5) 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.

6) We continue the previous exercise 8 by allowing a single person to
   disappear (switch off the phone, etc.), but still no message is lost.
   The person can disappear in any stage of the agreement. If other
   persons are able to agree, they do not need to care about the
   disappeared person.