Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Brown, Neil C.C.; Smith, Marc L. (2008)
Publisher: IOS Press
Languages: English
Types: Unknown
Subjects: QA76
Communicating Sequential Processes (CSP) was developed around a formal algebra of processes and a semantics based on traces (and failures and divergences). A trace is a record of the events engaged in by a process. Several programming languages use, or have libraries to use, CSP mechanisms to manage their concurrency. Most of these lack the facility to record the trace of a program. A standard trace is a flat list of events but structured trace models are possible that can provide more information such as the independent or concurrent engagement of the process in some of its events. One such trace model is View-Centric Reasoning (VCR), which offers an additional model of tracing, taking into account the multiple, possibly imperfect views of a concurrent computation. This paper also introduces ''structural'' traces, a new type of trace that reflects the nested parallelism in a CSP system. The paper describes the automated generation of these three trace types in the Communicating Haskell Processes (CHP) library, using techniques which could easily be applied in other libraries such as JCSP and C++CSP2. The ability to present such traces of a concurrent program assists in understanding the behaviour of real CHP programs and for debugging when the trace behaviours are wrong. These ideas and tools promote a deeper understanding of the association between practicalities of real systems software and the underlying CSP formalism.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] C. A. R. Hoare. Communicating Sequential Processes. Prentice-Hall, 1985.
    • [2] A.W. Roscoe. The Theory and Practice of Concurrency. Prentice-Hall, 1997.
    • [3] Peter H. Welch and Fred R. M. Barnes. Communicating mobile processes: introducing occam-pi. In 25 Years of CSP, volume 3525 of Lecture Notes in Computer Science, pages 175-210. Springer Verlag, 2005.
    • [4] N.C.C. Brown. Communicating Haskell Processes: Composable explicit concurrency using monads. In Communicating Process Architectures 2008, September 2008.
    • [5] Formal Systems (Europe) Ltd. Failures-Divergence Refinement: FDR2 Manual. 1997.
    • [6] Marc L. Smith, Rebecca J. Parsons, and Charles E. Hughes. View-Centric Reasoning for Linda and Tuple Space computation. IEE Proceedings-Software, 150(2):71-84, April 2003.
    • [7] Marc L. Smith. Focusing on traces to link VCR and CSP. In East, Martin, Welch, Duce, and Green, editors, Communicating Process Architectures 2004, pages 353-360. IOS Press, September 2004.
    • [8] Tim Harris, Simon Marlow, Simon Peyton-Jones, and Maurice Herlihy. Composable memory transactions. In PPoPP '05, pages 48-60. ACM, 2005.
    • [9] P.H. Welch, F.R.M. Barnes, and F.A.C. Polack. Communicating complex systems. In Michael G Hinchey, editor, Proceedings of the 11th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS-2006), pages 107-117, Stanford, California, August 2006. IEEE. ISBN: 0-7695-2530- X.
    • [10] P.H. Welch. Emulating Digital Logic using Transputer Networks (Very High Parallelism = Simplicity = Performance). International Journal of Parallel Computing, 9, January 1989. North-Holland.
    • [11] P.H. Welch, G.R.R. Justo, and C.J. Willcock. Higher-Level Paradigms for Deadlock-Free HighPerformance Systems. In R. Grebe, J. Hektor, S.C. Hilton, M.R. Jane, and P.H. Welch, editors, Transputer Applications and Systems '93, Proceedings of the 1993 World Transputer Congress, volume 2, pages 981-1004, Aachen, Germany, September 1993. IOS Press, Netherlands. ISBN 90-5199-140-1.
    • [12] J.M.R. Martin, I. East, and S. Jassim. Design Rules for Deadlock Freedom. Transputer Communications, 3(2):121-133, September 1994. John Wiley and Sons. 1070-454X.
    • [13] J.M.R. Martin and P.H. Welch. A Design Strategy for Deadlock-Free Concurrent Systems. Transputer Communications, 3(4):215-232, October 1996. John Wiley and Sons. 1070-454X.
    • [14] A. W. Roscoe and Naiem Dathi. The pursuit of deadlock freedom. Information and Computation, 75(3):289-327, December 1987.
    • [15] Mark Burgin and Marc L. Smith. Compositions of concurrent processes. In F.R.M. Barnes, J.M. Kerridge, and P.H. Welch, editors, Communicating Process Architectures 2006, pages 281-296. IOS Press, September 2006.
    • [16] Rance Cleaveland and Scott A. Smolka. Strategic directions in concurrency research. ACM Computing Surveys, 28(4), January 1996.
    • [17] C. A. Petri. Kommunikation mit automaten. Technical report, Schriften des IIm 2, Institut fur Instrumentelle Mathematik, Bonn, 1962.
    • [18] W. Reisig. Petri Nets-An Introduction, volume 4 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, New York, 1985.
    • [19] G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information Processing 74, North-Holland, Amsterdam, 1974.
    • [20] A. Mazurkiewicz. Trace theory. In W. Brauer, W. Reisig, and G. Rozenberg, editors, Petri Nets: Applications and Relationships to Other Models of Concurrency, Advances in Petri Nets, 1986, Part II; Proceedings of an Advanced Course (Bad Honnef, Sept.), volume 255 of Lecture Notes in Computer Science, pages 279-324, Berlin, 1987.
    • [21] V. R. Pratt. Modeling concurrency with partial orders. Int. J. Parallel Program., 15(1):33-71, 1986.
    • [22] G. Winskel. An introduction to event structures. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, REX School and Workshop on Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, volume 354, pages 364-397, New York, 1989. Springer-Verlag.
    • [23] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565, 1978.
    • [24] C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the 11th Australian Computer Science Conference (ACSC'88), pages 56-66, February 1988.
    • [25] D.A. Khotimsky and I.A. Zhuklinets. Hierarchical vector clock: Scalable plausible clock for detecting causality in large distributed systems. In Proc. 2nd Int. Conf. on ATM, ICATM'99, pages 156-163, 1999.
    • [26] Thomas Bo¬®ttcher and Frank Huch. A debugger for concurrent haskell. In Implementation of Functional Languages 2002, pages 129-141, 2002. Draft Proceedings.
    • [27] Jan Christiansen and Frank Huch. Searching for deadlocks while debugging concurrent haskell programs. SIGPLAN Not., 39(9):28-39, 2004.
    • [28] F.R.M. Barnes. Compiling CSP. In P.H. Welch, J. Kerridge, and F.R.M. Barnes, editors, Communicating Process Architectures 2006, pages 377-388. IOS Press, September 2006. ISBN: 1-58603-671-8.
  • No related research data.
  • No similar publications.

Share - Bookmark

Download from

Cite this article