School of Computing

Santa claus: Formal analysis of a process-oriented solution.

Peter H. Welch and Jan B. Pedersen

ACM Transactions on Programming Languages and Systems, 32(4):14:1-14:37, April 2010 [doi].

Abstract

With the commercial development of multicore processors, the challenges of writing multi-threaded programs to take advantage of these new hardware architectures are becoming more and more pertinent. Concurrent programming is necessary to achieve the performance that the hardware offers. Traditional approaches present concurrency as an advanced topic: they have proven difficult to use, reason about with confidence, and scale up to high levels of concurrency. This paper reviews process oriented design based on Hoare's algebra of Communicating Sequential Processes (CSP), and proposes that this approach to concurrency leads to solutions that are manageable by novice programmers -- that is, they are easy to design and maintain, that they are scalable for complexity, obviously correct and relatively easy to verify using formal reasoning and/or model checkers. These solutions can be developed in conventional programming languages (through CSP libraries) or specialised ones (such as occam-pi) in a manner that directly reflects their formal expression. Systems can be developed without needing specialist knowledge of the CSP formalism, since the supporting mathematics is burnt into the tools and languages supporting it. We illustrate these concepts with the Santa Claus Problem which has been used as a challenge for concurrency mechanisms since 1994. We consider this problem as an example control system, producing external signals reporting changes of internal state (that model the external world). We claim our occam-pi solution is correct-by-design but follow this up with formal verification (using the FDR model checker for CSP) that the system is free from deadlock and livelock, that the produced control signals obey crucial ordering constraints, and that the system has key liveness properties. Download publication 613 kbytes (PDF)

Bibtex Record

@article{3065,
author = {Peter H. Welch and Jan B. Pedersen},
title = {Santa Claus: Formal analysis of a process-oriented solution.},
month = {April},
year = {2010},
pages = {14:1-14:37},
keywords = {process orientation, concurrency, deadlock, event ordering, liveness, verification, novice programmer, occam-pi, CSP},
note = {},
doi = {10.1145/1734206.1734211},
url = {http://www.cs.kent.ac.uk/pubs/2010/3065},
    publication_type = {article},
    submission_id = {11019_1289238674},
    journal = {ACM Transactions on Programming Languages and Systems},
    volume = {32},
    number = {4},
    publisher = {Association for Computing Machinery},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 12/03/2012 17:31