D32 Scalability

Overview

Regarding scalability of the Rodin platform, the following contributions has been made:

• (Alexei) Flow plug-in

• (Alexei) Group Refinement

• (Alexei) Modes

• Emre Yilmaz and Thai Son Hoang (ETH Zurich) has developed a plug-in supporting an extension of Event-B with qualitative reasoning. The extension allows developer to declare an event converges probabilistically (with probability 1). This is in contrast with standard certain termination, where convergent events must decrease the declared variant. Provided that the variant is bounded above, an event probabilistically converges if it might decrease the variant. The extension enables Event-B to model systems with almost certain termination properties, e.g. IEEE 1394 Firewire protocol or Rabin's Choice Coordination algorithm .

Motivations

Flow plug-in

(Alexei)

Group Refinement

(Alexei)

Modes

(Alexei)

Qualitative Reasoning

Probability is used in many distributed systems for breaking the symmetry between different components/processes, e.g. IEEE 1394 Firewire protocol , Rabin Choice Coordination algorithm . For such systems, termination cannot be guaranteed for certain. Instead, a slightly weaker property is mostly appropriate: termination with probability one. As an example for this type of systems is to consider tossing a coin until it comes up tail. Provided that the coin is fair (in that sense that no face is ignored forever), eventually, the coin will eventually come up head.

Qualitative probabilistic reasoning has been integrated into Event-B : a new kind of actions is added, namely probabilistic actions with an assumption that the probability for each possible alternative is bounded away from 0 or 1. Most of the time, probabilistic actions behave the same as (standard) non-deterministic actions (e.g. invariant preservation). The difference between probabilistic and non-deterministic actions is with convergence proof obligation: probabilistic actions are interpreted angelically, whereas non-deterministic actions are interpreted demonically. The result is a practical method for handling qualitative reasoning that generates proof obligations in the standard first-order logic of Event-B.

The plug-in allows developers to declare an event to be probabilistic convergent and generate appropriate proof obligations. Since the obligations are in standard first-order logic supported by the Rodin platform, we do not need to make any extension for the provers to handle the new proof obligations.

Choices/Decisions

Flow plug-in

(Alexei)

Group Refinement

(Alexei)

Modes

(Alexei)

Qualitative Reasoning

• Ideally, we would like to have a new value for the convergence attribute of Event-B events. However, this is not currently supported by the Rodin platform. Instead, a new probabilistic attribute is defined for events, with the value is either standard or probabilistic.

• Since standard refinement does not maintain probabilistic convergent property, we put a restriction on the development method for almost-certain termination systems in two steps as follows.
  1. Establish the model of the systems with various anticipated events
  2. While proving convergence properties of events (either standard or probabilistic), we keep the variable and event system the same (i.e. no refinement is allowed).

• For probabilistic convergence, the variant need to be bounded above. A combination of standard and probabilistic convergence events results in a probabilistic convergence system. Moreover, the use of anticipated events and refinement allowed us to construct an lexicographic variant by combining the sub-variant at different level of refinements. For probabilistic convergence system, this lexicographic variant need to be bounded above, which require all the sub-variants to be bounded above (not only those variant concern with probabilistic events).

More details of our approach is in our report at AVoCS'10 .

Available Documentation

• Master thesis of Emre Yilmaz on developing tool support for qualitative reasoning in Event-B .

• The development of Rabin's Choice Coordination Algorithm is available at the DEPLOY Repository .

• A paper describing the development of Rabin Choice Coordination algorithm and tool support in the Proceedings of AVoCS'10 .

Planning

Flow plug-in

(Alexei)

Group Refinement

(Alexei)

Modes

(Alexei)

Qualitative Reasoning

In DEPLOY's fourth year, we plan to implement the missing proof obligations. More importantly, we will investigate the interaction between refinement and almost certain termination. This allows us to prove convergence properties early in the development and make sure that refinement will maintain these convergent properties.