Probabilistic Methods in Concurrency

(Concurrent Languages for Probabilistic Asynchronous Communication)

PhD Course, Pisa, 28/6 - 15/7/2004

Catuscia Palamidessi

[ Lectures ] [ Bibliography ] [ Exam ]


  1. The pi-calculus and the asynchronous pi-calculus. Lecture notes (ppt , pdf).

  2. The pi-calculus hierarchy: encodings. Lecture notes (ppt , pdf).

  3. The pi-calculus hierarchy: separation results (ppt , pdf).

  4. Problems in distributed systems for which only randomized solutions exists (ppt , pdf).

  5. Basics of Measure Theory and Continuous Probability Theory. Probabilistic Automata (ppt , pdf).

  6. A tool for verification of probabilistic automata: Progress Statements (ppt , pdf).

  7. The probabilistic pi-calculus (ppt , pdf).

  8. Encoding of the pi-calculus into the probabilistic asynchronous pi-calculus (ppt , pdf).

  9. Other uses of randomization: a randomized protocol for anonymity (ppt , pdf).

  10. A proof search specification of the pi-calculus (speaker: Dale Miller) (pdf).



The exam consists in solving some exercises of the list enclosed below. Each exercises is worth a number of points. You can select the exercises you want, up to 20 points (if you solve more than 20 points exercises, the score will be anyway renormalized to 20). Please send me the solution by email by September 30, 2004.

List of exercises

  1. [5 points] Show two pi-calculus processes, P and Q, which are early bisimilar but not late bisimilar. P and Q must be written using only prefix, parallel, sum, and 0. (Ref. Lecture 1.)

  2. [10 points] Let [[]] be the encoding of Honda-Tokoro of the output prefix into the asynchronous pi-calculus. Say whether this encoding is 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. (Ref. Lecture 2.)
    For the definition of weak bisimilarity see, for instance, Sangiorgi and Walker's book on the pi-calculus, or Milner's book on the pi-calculus. For this exercise the difference between early and late is unessential.)

  3. [5 points] 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. (Ref. Lecture 3.)

  4. [10 points] 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. Justify your answer using the progress statements of Segala-Lynch (Ref. Lectures 4 and 6.)

  5. [5 points] 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. (Ref. Lecture 5).

  6. [5 points] Consider the randomized algorithm for the dining cryptographers (Ref. Lecture 9). Write this algorithm using the probabilistic asynchronous pi-calculus. (Ref. Lecture 7).

  7. [10 points] 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. (Cfr. Lectures 7 and 8.)