Xmas code crackers

The ‘Santa Claus Problem’ (outlined above) was first described by Professor John A. Trono, (of Saint Michael’s College, VT, US)  in his paper ‘A new exercise in concurrency’, SIGCSE Bulletin, Vol. 26, pp. 8-10, 1994. Despite its apparent first-glance simplicity, the problem presents robust concurrent programming complexities when using ‘traditional’ computer programming languages such as  C  (circa 1970) . Encouraging others like, for example, Mordechai Ben-Ari of the Weizmann Institute of Science, Israel, to try tackling the problem using more modern languages such as Ada  (circa 1980 ) and Java (circa 1995). See: M. Ben-Ari. How to solve the santa claus problem. Concurrency: Practice & Experience, 10(6):485–496, 1998.

Although Ben-Ari’s methods provided an apparent improvement, if one takes the approach that shorter, simpler algorithmic solutions are more elegant, one might instead plump for the resources of an even newer programming language like Polyphonic C# designed and implemented (circa 2002) by Nick Benton, Luca Cardelli and Cédric Fournet of Microsoft Research, Cambridge, UK.

By way of a  demonstration, Dr. Nick Benton, who is now a Senior Researcher at Microsoft Research in Cambridge constructed a new algorithmic solution. His (as yet unpublished) paper Jingle Bells: Solving the Santa Claus Problem in Polyphonic C# not only outlines possible pitfalls for programmers :

“The errors which are easy to make in an attempt to solve this problem include extra elves being able to sneak into a group once Santa has started showing elves into his office, or Santa being able to go off delivering toys whilst the reindeer are still waiting in the stable.”

but goes on to provide a polyphonic C# solution – and points out that :

“This provides another small piece of evidence that Join calculus-based concurrency primitives, as well as being a good basis for distributed computation, are a very attractive choice for solving traditional concurrency problems.”

  • Mikaël

    The last reference in Trono’s paper is by someone named “Tanenbaum”…