Using Occam to Simulate p2p Web Services

About a year ago I gave a paper at an IEEE E-Commerce conference that described how I used the latest pi-calculus enhanced version of the old Inmos Transputer language Occam to build a very efficient massively threaded simulator for large scale p2p web services that ran on my laptop.

I blogged this at the time, but The paper itself is subject to the rules IEEE sets out for peer-reviewed conference papers and you need to be a member or pay a fee to get it from http://doi.ieeecomputersociety.org/10.1109/CEC-EEE.2006.81

However, I wanted to share this more widely and have just posted a pdf of the presentation slides for my IEEE paper. Here are the first few slides, and a description of the Tools section:

Simulation of Skype Peer-to-peer Web Services Choreography Using Occam-Pi

Abstract
Complex web services are very difficult to test and verify before deployment on a large scale.
A semantically equivalent in-memory simulation can be built using Occam-pi that runs up to 100,000 nodes about a million times faster than real life.
Rapid protocol development and detailed behavioral analysis using simulation supports the development of robust services that can scale.
The implementation of a simulator that models centralized web services and application to application messaging over the Skype Peer to Peer network is described.

Overview

• The Landscape
• The Problem
• The Tools
• The Solution
• Implementation
• Running the Simulation
• Conclusion
• References

The Tools – Pi Calculus

• WS-BPEL, SSDL and WS-CDL are based on Pi-Calculus
• Pi-Calculus is based on Communicating Sequential Processes (CSP)
• Pi-Calculus provides a formal model of parallel message based computing
• Occam-Pi
• The Occam language is based on CSP, and has been extended to add the Pi-Calculus extensions to form the Occam-Pi language.
• The primary implementation of this language is known as KROC, the Kent Re-targetable Occam Compiler
• KROC is freely available from the University of Kent at Canterbury, UK
• Runs on Intel architecture Linux, MacOS X, and Microsoft Windows/Cygwin platforms. Older versions exist for SPARC, PPC etc.

The Tools – Occam Language Constructs

• The constructs that are used in Web Services choreography map directly to Occam language constructs
• The Occam language has direct support for sequential, parallel and alternate processing blocks, complex protocols, and channel based communications
• Occam-Pi adds more dynamic constructs to the language
• Mobile channels - pass a channel end over another channel
• Mobile processes - suspend a process, pass it over a channel and resume it in a new context
• Dynamic process forking with barrier synchronization
• Rigorous Occam-Pi Compile-time Checks
• Processes or expressions are not allowed to have any “side effects”
• Syntax and usage of all protocols, data and constructs is checked
• Occam is designed to allow very comprehensive static analysis

The Tools – Occam Runtime Characteristics

• There is no need to use XML message encoding or namespaces
• since the compiler can check that a protocol is being communicated correctly
• At runtime, the Occam-Pi language is fast small compiled code
• with its own threading model, in a single process
• The Occam-Pi runtime detects and reports deadlock
• including the line number in the code at which each process was stalled
• Occam-Pi is very efficient
• All communication takes place in a single address space at memory bus speeds
• Basic process creation takes 20 nanoseconds on an 800MHz PC
• Basic channel communications takes 70 nanoseconds
• Compared to typical web services transactions over the internet these transactions are about a million times faster
• The language is also very compact, and one hundred thousand to one million threads can be created within a 2 GByte address space.

Works Cited

• [Cygwin] “GNU + Cygnus + Windows”, http://www.cygwin.com/
• [GraphML] “Graph Modeling Language “, http://graphml.graphdrawing.org/
• [Hoare78] C. A. R. Hoare. “Communicating Sequential Processes.” Communications of the ACM 1978.
• [Hoare85] C. A. R. Hoare. Communicating Sequential Processes. Prentice Hall, 1985.
• [KROC]. “Kent Retargetable Occam Compiler” http://www.cs.kent.ac.uk/projects/ofa/kroc/
• [Occam2] Inmos Ltd, Occam 2 Reference Manual. Prentice Hall, 1988.
• [Milner99] Robin Milner, “Communicating and Mobile Systems: the Pi-Calculus”, Cambridge University Press, 1999.
• [Skype]. “Skype Developers API” https://developer.skype.com
• [SSDL] Webber et al. “Asynchronous Messaging between Web Services using SSDL.” IEEE Internet Computing Vol10, No1 2006.
• [WS-BPEL]. “OASIS Web Services Business Process Execution Language” http://www.oasis-open.org
• [WS-CDL] “Web Services Choreography Description Language”, http://www.w3.org
• [yEd] “Graph visualization and editing tool”, http://www.yworks.com/