MPRI 2006-07 - Cours 2-3: Concurrence

Exercises for the part of Palamidessi

  1. Consider the encodings of Boudol and Honda-Tokoro of the output prefix into the asynchronous pi-calculus (cfr. Lecture 15, Pages 7 and 8). Say whether these encodings are fully abstract wrt weak bisimulation. Namely, say whether it is true that P is weakly bisimilar to Q iff and only if [[P]] is weakly bisimilar to [[Q]]. Justify your answer.
    Note: For this exercise the difference between early and late weak bisimulation is unessential.

  2. Prove the first Theorem at page 10 of Lecture 15.

  3. A fair computation is a computation in which each non-blocked process in a parallel composition gets to make a step sooner or later. Define formally the notion of fair computation. Furthermore, define the notion of fair must (like the must testing, but in which the only computations to be considered are the fair ones) and prove the second theorem at page 10 of Lecture 15.

  4. Consider the result of Nestmann and Pierce, at page 12 of Lecture 15. Show that the result does not hold if we replace coupled bisimulation by weak bisimulation.

  5. Modify the definition of the Leader Election Problem in such a way that it is only the winner to output the result (the name of the winner), while the losers don't do aything. Does this version of the problem still separates the pi-calculus and the asynchronous pi-calculus? Justify your answer.

  6. Give a ring with three symmetric processes, write a program for them in the pi-calculus solving the leader election problem.

  7. Given a ring of n symmetric processes, write a program for them in the pi-calculus solving the leader election problem.

  8. Consider Lehmann e Rabin's randomized algorithm for the dining philosophers. Consider the following modification: In line 3, replace goto 3 with goto 2. Namely, instead of doing busy waiting on the selected fork (first fork), the philosopher goes back and redo the random choice. Say whether this algorithm is still correct, i.e. whether it ensures with probability 1 that, for every fair scheduler, if a philosophe is hungy, then eventually a philosopher will eat. Also, answer the same question for unfair schedulers.

  9. Consider a finite set X, let Sigma be the set of all powersets of X, and define the function mu : Sigma -> [0,1] as mu(A) = #(A)/#(X), where #(A) is the cardinality of A. Is (X, Sigma, mu) a probability measure space? Justify your answer.

  10. Consider the randomized algorithm for the dining cryptographers. Write this algorithm using the probabilistic asynchronous pi-calculus.

  11. Consider the following process in probabilistic asynchronous pi-calculus (where x^y represents the action of sending on x the name y):
    P = recA (1/2 tau . A + 1/2 tau . x^y)
    Consider the following tester
    T = tau . x(z) . omega
    Say whether P must T with probability 1, or not, for
    1. every fair scheduler,
    2. every scheduler
    Justify your answers.