CSE5XX Distributed Computing 2020 Winter • MidSem • 100 points Given to you: Feb 22, 2020, 8:00 PM; Due: Feb 23, 11:59 PM.

This take-home exam permits the use of a Linux/Windows laptop/PC running javac, g++, Eclipse, Idea, and other software development and drawing tools. It is otherwise a traditional closed book, closed notes exam. In particular, you are honor bound *not* to Internet surf or access any content already existing (other than as indicated) once you access the exam until you turnin the answers. The primary reasons in making this a take-home are to relieve time pressure and give you a comfortable (computing/home) environment. Do not give or take help from others.

Submit your answers.pdf as an email attachment to me.

1. (5 points each) The following statements may or may not be (fully or partially) valid. Explain the underlined technical terms occurring in each statement. Explain/ discuss/ dispute the statement. It is possible to write no more than, say, five, lines each, and yet receive full score.
   1. ``Some philosophers may remain hungry forever.'' is a safety, not liveness, property.
   2. In the context of RPC, a procedure designed to be used remotely can use global variables to communicate with the caller.
   3. Consider the program segment given here.

      Determine P a predicate that characterizes the weakest deadlock-free precondition for the program. Also, explain how you arrived at P.

      co <await x >= 7 -> x := x - 3> || <await x >= 6 -> x := x + 1> || <await x >= 5 -> x := x + 1> oc

   4. Compute wp(S, i = 100), where S is
      if i < 150 then i := i + 150 else i := 100 fi
2. (20 points each)
   1. In the distributed programming context, P(m); Critical-Section; V(m) is not starvation-free. Give a detailed starvation scenario. What does Morris' algorithm do to eliminate this scenario?
   2. Construct the ssend(pid, msg) and srecv(pid, msg) primitives of synchronous message passing from asend(pid, msg) and arecv(pid, msg) primitives of asynchronous message passing.
   3. Reconstruct the binary "tree" serialized below. List each node as a triplet of (info integer, left-link and right-link), as usual.  The first digit in the sequence is the offset of the root node.
      marshalled sequence: 2 3 4 7 4 7 8 4 A 1 4 2 7
      offsets in hex:      1 2 3 4 5 6 7 8 9 A B C D
   4. The Recursive Data Representation: Small Set of Integers of Hoare's CSP paper is reproduced below. Extend it to respond to a command S(1)!remove(x) from S(0) that removes x from the set, if it contains it, and does nothing if it does not.

          S(i: 1 .. 100) ::
          *[   n: integer; S(i-1)?has(n) --> S(0)!false
           []  n: integer; S(i-1)?insert(n) -->
                  *[  m: integer; S(i-1)?has(m) -->
                       [   m <=  n --> S(0)!(m = n)
                       []  m >   n --> S(i+1)!has(m)
                       ]
                   [] m: integer; S(i-1)?insert(m) -->
                       [  m < n --> S(i+1)!insert(n); n := m
                       [] m = n -->  skip
                       [] m > n --> S(i+1)!insert(m)
           ] ] ]

3. (0 points) [For survey purposes only.] Please record your effort in minutes for each of the above ten eight items. Other feedback you wish to give is also welcome.