Homework 9 Solutions

22C:116, Spring 1997

Problem 1 part A:

    The ISO OSI protocol hierarchy addresses this problem at the
    PRESENTATION level.

Problem 1 part B:

    In the context of RPC relationship between client and server,
    any data format conversion is done at the client and/or server
    stubs level.  In practice both stubs convert any data format to
    the "standard" network format and back from the standard to
    their own format.

    Other strategies one may imagine could make the client stub send
    first it's data format and the server stub would convert it to
    its own format.  Using a canonical format for is computationally
    easier because it means that each stub need know only 2 formats,
    the local format and the canonical format.  If the local and
    canonical formats are the same, the stub need do no work.

Problem 2 part A:

    Clock drift rate is the amount a real clock reading deviates from
    the "ideal" clock's value.  The difference between two clocks that
    have the same initial value, can be, after one second (assuming
    the drift rates are given in seconds per second) as much as double
    the maximum drift, if the clocks drift in opposite directions.

    Let us assume that the synchronization algorithm sets the two
    clocks on the link to the mean value of the two readings.
    Consider a linear network with 11 processors and 10 links, where
    Let's say P0 has drift -0.01 and all P1 - P10 have drifts of
    +0.01.  Assume that synchronization is done in the order: P10-P9,
    P9-P8, ,,,P1-P0.  This is a bad case, because the error will
    take 10 seconds to reach P10.  For the first 9 seconds P10 will
    run in phase with P9, so no adjustment is done to the clock value
    since they have similar clock drifts.

    Using a simple simulation, the maximum error observed in this
    situation was 0.04 seconds.  A simple theoretical argument
    suggests that the maximum observed error will grow as O(n) where
    n is the diameter of the network.

Problem 2 part B:

    The drift of a composite clock is equal to the mean of the
    individual drifts of the component clocks (sum of all the drifts
    over the number of clocks).

    Since individual closk drift rates are randomly distributed over
    the allowable range of drift rates, both in value and in sign
    (lower vs faster clocks, the sum of all the 100 drifts of the
    clocks is very close to 0. Dividing it by 100 makes it even
    smaller so we can expect a very high accuracy for the composite
    clock.

    Recalling elementary statistics, if N independent measurements
    of the same quantity are averaged, where each measurement has an
    expected error of e, the expected error in the average is
    e/sqrt(N) -- so the composite of 100 clocks, where each has an
    expected drift of d, will have an expected drift of d/10.

Problem 3:

    Each process i keeps local copies of the arrays C[i] and N[i]:
           _ _ _ _ _ _ _ _ _ _ _
        C |_|_|_|_|_|_|_|_|_|_|_|
        N |_|_|_|_|_|_|_|_|_|_|_|

    The main idea to reduce the trafic of messages compared to the original
    algorithm is analogous to the comaparison between polling and interrupts.
    Instead polling each process j about its state C[j] and N[j],
    each process j will broadcast to all other processes its state only
    when it modifies it. To be sure that the messages are received by their
    destinations, the sender waits for acknowledges from all receivers.
    In this way the trafic is moved from evaluation of C and N to assignment
    of C and N. The new version is better because there are exactly 6N
    messages not more:

        2N messages when C[i] := 1;
        2N messages when N[i] := max(...)+1; and C[i] := 0;
        2N messages when N[i] := 0;

    In the original version, C[j] and N[j] are checked in busy waiting loops,
    each checking involving 2N messages, so the total number of messages
    may be very large.

    The algorithm is the same, with the observation that when C[i] or
    N[i] is modified, the process i will broadcast the new values and
    wait for the acknowledges from all other processes.  When a process
    receives a message, an interrupt routine is called which updates
    the corresponding entries in the local arrays C and N and sends the
    acknowledge to the sender.

Problem 4 part A:

    Mutual exclusion algorithms are needed whenever there is a shared
    data involved, while election algorithms are run whenever a fault
    causes a special authority process to fail.

    Mutex algorithms are hard to conceive in the presence of faults
    (most assume faults are not allowable), while election algorithms
    are designed for faulty medium.

    In mutex algorithms fairness is an important issue and the process
    trying to enter the critical section must succeed eventualy. In
    election algorithms the intiator need not be the winner and fairness
    is not an issue.

    In mutex algorithm one process only needs to know if it is the
    winner or not, in election algorithms all currently alive processes
    must agree upon the same winner.

    In a mutex algorithm only the processes interested to enter the
    critical section participate ( may happen that all need to do that),
    while in an election algorithm all alive processes must participate.

Problem 4 part B:

    Mutual exclusion algorithm based one a centralized authority cannot
    be modified to serve the purpose of election since in the presence
    of a fault of the "authority" the whole system fails for good.
    Distributed mutual exclusion algorithms, in which every process has
    the same code, can be transformed to perform election. The algorithm
    is initiated by a process that dicovers the failure af the leader
    (instead of a process that wants to enter the critical section). All
    the other processes respond as if they all want to enter the critical
    section. Finally , the winner lets everyother process know its
    identity. Apart from those three modifications the algorithm runs
    as it did for the mutual exclusion problem.