MPRI 2006-07 - Cours 2-3: Concurrence
Exercises for the part of Palamidessi
-
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.
- Prove the first Theorem at page 10 of Lecture 15.
- 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.
-
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.
-
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.
-
Give a ring with three symmetric processes, write a program for them in the pi-calculus solving the leader election problem.
-
Given a ring of n symmetric processes, write a program for them in the pi-calculus solving the leader election problem.
- 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.
- 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.
- Consider the randomized algorithm for the dining
cryptographers. Write this algorithm using the
probabilistic asynchronous pi-calculus.
- 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
- every fair scheduler,
- every scheduler
Justify your answers.