Logic in Computer Science (LICS 2002)

Paper: The Metric Analogue of Weak Bisimulation for Probabilistic Processes (at LICS 2002)

Authors: Josee Desharnais Vineet Gupta Radha Jagadeesan Prakash Panangaden

Abstract

Weak bisimulation for probabilistic processes has been a difficult concept to define properly but satisfactory definitions have recently become available. As in earlier work, we observe that equivalence is not a robust concept in the presence of numerical information - such as probabilities - in the model. We develop a metric analogue of weak bisimulation in the spirit of our earlier work on metric analogues for strong bisimulation. The theory, however, is quite different from our earlier treatment and surprisingly smoother than expected. We give a fixed point characterization of the metric. This makes available coinductive reasoning principles and allows us to prove metric analogues of the usual algebraic laws for process combinators. We also show that quantitative properties of interest are continuous with respect to the metric, which says that if two processes are close in the metric then observable quantitative properties of interest are indeed close. As an important example of this we show that nearby processes have nearby channel capacities - a quantitative measure of their propensity to leak information.

BibTeX

  @InProceedings{DesharnaisGuptaJaga-TheMetricAnalogueof,
    author = 	 {Josee Desharnais and Vineet Gupta and Radha Jagadeesan and Prakash Panangaden},
    title = 	 {The Metric Analogue of Weak Bisimulation for Probabilistic
    Processes},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2002},
    year =	 2002,
    editor =	 {Gordon Plotkin},
    month =	 {July}, 
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }