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
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.
- The Landscape
- The Problem
- The Tools
- The Solution
- Running the Simulation
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
- 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.
- [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/