Compositional Programming Together With Testing Of Dynamic Distributed Systems

This paper is authored past times Ankush Desai, Amar Phanishayee, Shaz Qadeer, together with Sanjit A. Seshia, together with it appeared at OOPSLA 2018.

The newspaper describes the ModP framework extension over the P language. P is a linguistic communication developed for condom event-driven programming. P models processes equally nation machines: the nation machines communicate via message passing, together with events drive nation machines to transition betwixt states. 

The killer characteristic of P is unifying modeling amongst programming! P enables the programmers to write specifications together with enables systematic testing both via random testing together with exhaustive symbolic execution testing.

P is used inward result driven systems such equally device drivers together with robotics. The P GitHub page states that P is used inward Microsoft (P# together with Coyote) together with likewise used extensively at AWS for model-based testing of complex distributed systems.  

Compositional testing of distributed systems

A employment amongst systematic testing is that monolithic testing of large systems neglect due to combinatorial nation infinite explosion. Achieving total coverage testing of a large monolithic organisation takes forever. The ModP framework extension inward this newspaper addresses this problem. 

To make scalability of systematic testing, *decomposition* is used. ModP shows how to decompose the monolithic system-level testing employment to component-level testing problems, together with how to make scalable model-based integration testing of distributed systems.

In guild to elevator the component-level testing to the  whole system-level, ModP employs the theory of assume-guarantee (AG) reasoning (also known equally rely-guarantee reasoning). This is a classic sentiment inward formal methods proposed to a greater extent than than xxx years ago. Assume-guarantee starts amongst each constituent specifying its assume from its surroundings together with its provided guarantee inward render virtually its transitions. Note that a component's surroundings is formed past times the other components it volition locomote composed with. Thus if a component's assume is satisfied past times the combined guarantees provided past times the other components, nosotros tin sack banking firm on the guarantee from that component. Therefore the AG theorem states that it is possible to accept the conjunction of all components' AG specifications together with derive the organisation AG specification.

In the ModP testing approach, each constituent is outset automatically tested for showing refinement amongst honour to the corresponding abstract modules together with specifications. Then each constituent is composed amongst the abstract versions of the other components (as inward mocking but to a greater extent than rigorously now) together with is tested for organisation score specifications. This testing tin sack locomote done using randomized belongings testing or via using meliorate coverage symbolic execution testing.

Composing the concrete implementations Two Phase Commit together with MultiPaxos SMR together with testing them together monolithically would non run due to nation infinite explosion. So ModP composes Two Phase Commit amongst the abstract version of MultiPaxos SMR, the SMR abstraction, together with tests them first. Then ModP composes MultiPaxos SMR amongst the abstract version of Two Phase Commit, SMR customer to brand certain in that place is no incompatibility in that place either. Finally past times using the AG theorem, ModP infers the concrete versions of the ii components composed would likewise render the same correctness properties. An added bonus is that if nosotros afterwards desire to swap Chain Replication amongst MultiPaxos, nosotros produce non ask to repeat the Two Phase Commit together with SMR abstraction exam again. We only perform Chain Replication together with SMR customer tests. 

The ModP approach adds rigor to the traditional integration testing, together with achieves a real adept coverage. The toll to the programmer is to write the abstract modules together with specifications to exam with. It does non render equally adept coverage equally proof based approaches similar Dafny together with Armada. However, proof-based approaches incur high overhead for the programmer inward coming upward amongst the proof hints together with fifty-fifty together with then produce non scale good to large systems, peculiarly to distributed systems, due to the combinatorial nation infinite explosion problem. 

In the context of distributed systems, the AG reasoning likewise gets somewhat complicated due to the dynamicity involved: the processes are created *dynamically* together with the communication topology may likewise alter *dynamically*. Most of the intelligence inward the newspaper is virtually the technical workarounds that were required to brand the AG theory run elegantly inward this dynamic model. To brand this work, ModP introduced interfaces, input-event-hiding rule, together with a well-formedness banking firm check that reinforces output (send result together with interface) disjointness.zoo

Results

The newspaper demonstrated the mightiness of ModP's model-based integration testing framework past times edifice a transaction-commit service using ii stage commit together with MultiPaxos or Chain Replication. A pregnant finding inward the newspaper (Figure 13) is that in that place is a 100 folds reduction inward execution traces for testing when substituting an abstract module for the surroundings instead of testing against the concrete module.

Fig xiv shows that, past times enabling compositional testing, ModP achieves faster põrnikas finding amongst prioritized random search equally compared to monolithic testing. Moreover piece the symbolic execution completes inward 1.3 hours inward the decomposed system, it does non destination on the monolithic fifty-fifty after 10 hours.

The conference presentation from Ankush Desai is excellent, together with I nurture you lot to that, the newspaper pdf, together with the GitHub repo if you lot are interested to a greater extent than inward the P language. 

Share this post