[cs63201] on message complexity for Obermark's and CMH

[Mikhail Nesterenko]

AOS students,

This is on Chandy-Misra-Haas and Obermark's algorithms. The links to
the original papers are on the course's website. I advise you to read
the original papers as Singhal's description is not very precise.

Both algorithms assume that a process may wait for more than one
process. However, this is different from multiple resource instances
that we studied. For CMH and Obermark's it is assumed that the process
will not be able to make progress unless all processes that this
process is waiting for free their resources.

Thus, in the worst case the processes wait-for graph (WFG) is
completely connected. Assume that all links span sites.
Thus, the total number of external links is n(n-1)/2 where
n is the number of processes.

My message complexity estimate is as follows.

   For CMH, Each (process) initiator maintains a counter. Every time
   there is an external chain, the process increments the counter and
   sends a probe with this counter. Each process keeps the counter
   for all other processes and only sends the probe once (for each
   initiator and each counter).

   In the worst case, the probe for one initiator can traverse all
   edges in the WFG.

   In their (conference) paper CMH try to limit the number of
   initiators per deadlock by allowing only the processes that
   just obtained an incoming link in the WFG to initiate the probes.

   However, the cycle can be formed such that the links are formed
   in parallel. Hence every process becomes an initiator.

   Thus, the total number of messages in the worst case is n*n*(n-1)/2
   which is in O(n^3)

----

   For Obermark, the sites send a "path" to the other
   sites. Recall, that to decrease traffic Obermark proposes that
   only those sites send the path whose outgoing process identifier
   is less than incoming.

      BTW, I was not clear in class, Obermark proposes that the site
      sends the path only to the "downstream" with respect to the
      shared process (transaction). That is the site does not
      broadcast it to all other sites.

 Now, let us estimate the complexity of the algorithm.
 I find it a little easier to think of processes being inside the
 sites and the edges in the WFG being external. The reasoning,
 however, is similar in Obermark's notation.

   Suppose the identifiers of the processes are 1, 2, ..., n

   Suppose all WFG links are external and the higher id processes wait
   for the lower id ones (except for process 1 that waits for process
   n so that we have a deadlock)

   For simplicity, suppose there are n sites (one per process).
   Let us call the sites by the identifier of the process that resides
   there:
           1, 2, 3, ..., n

   In the worst case,

   - site 2 pushes process id 2 to site 1,
   - site 3  pushes process id 3 to sites 1 and 2
     -- this forces site 2 to push process id 3 to site 1.

    and so on

   Thus, process n identifier travels along all links, process (n-1)
   travels along all links except those leading to site n, and so on.

   Notice that the graph is completely connected. The total number of
   links is n(n+1)/2
   Thus, the number of links, process n travels is

      n(n+1)/2

   process n-1:   (n-1)n/2

   The total number of messages is:

   n(n+1)/2 + (n-1)n/2 + (n-2)(n-1)/2 + (n-3)(n-2)/2 + ....

   doing pairwise factoring we obtain

   [ n(n+1 + n-1)  + (n-2)(n-1+n-3) + ...] / 2

   simplify

   [ n * 2n + (n-2)(2n-4) + (n-4)(2n-8) + ...]/2

   factoring 2 we obtain

   n^2 + (n-2)^2 + (n-4)^2 + ...

   There is probably an exact formula for this series, but I just
   estimated it from above and below.

    Let us call the above sum A(n)

   It is known that

   n^2 + (n-1)^2 + (n-2)^2 + ...  = n(n+1)(2n+1)/6

   Let's call this sum B(n)

   Clearly, B(n) > A(n) since some of the addends of B(n) are missing
   from A(n). Let us estimate B(n) from below.

   Let us consider 2A(n) = 2n^2 + 2(n-2)^2 + ...
   it is smaller than
                        n^2 + (n-1)^2 + (n-2)^2 + (n-3)^2 + ...

   That is 2A(n) > B(n).

   Which means that B(n) > A(n) > B(n)/2

   Observe that both B(n) and B(n)/2 are in O(n^3)

   Therefore A(n) is in O(n^3).

That is, the worst case message complexity of Obermark's algorithm is
the same as that of CMH and it is cubic with respect to the number of
processes in the system.

Thanks,
--
Mikhail