CSC 2/458: Parallel and Distributed Systems

Spring 2026

Assignment 2: Distributed Control of Asynchronous Process Interactions
(Communication with output guards in CSP)

The purpose of this assignment is to expand your knowledge of multithreaded programming by solving a classic problem in synchronization.  In class we discussed the Dining Philsophers Problem, a pedagogical example introduced by Dijkstra in 1972.  For this assignment you will address a somewhat more realistic (but only slightly newer), problem. 

In 1978, C. A. R. (Tony) Hoare, one of the towering figures of programming language design (and winner of the 1980 Turing Award) published Communicating Sequential Processes (CSP), a notation for rich communication patterns in message-passing programs.  In Hoare’s notation, a server process that is willing to receive from any of several clients uses a selection command with input guards to specify the possible communication partners.  It waits until at least one of them is ready to send to it and then chooses from among them nondeterministically.  Symmetrically, a client that is willing to send to any of several servers uses a command with output guards to specify its potential partners, one of which is chosen nondeterministically.  (A single guarded command is actually allowed to include both input and output options.)  Significantly, communication is synchronous: both sender and receiver must agree to the exchange, at the same time, forgoing interaction (at least for now) with their other potential partners.  Each synchronous interaction is called a rendezvous

CSP-style guarded commands were the inspiration for communication in several programming languages—notably Ada and Go.  They also influenced the design of the Unix select system call.  It’s not immediately clear, however, how to “pair up” senders and receivers efficiently and fairly.  In practice, it turns out that servers selecting among clients is much more common than clients selecting among servers, and most systems—including Ada, Go, and Unix—have chosen to implement input guards but not output guards.  (One-sided selection is easy to implement: a client commits to a server, sends their request, and waits to be selected.) 

But conservative choices by system designers didn’t stop researchers from looking for good implementations of fully general CSP!  A flurry of potential algorithms were published in the 1980s.  Your task for this assignment is to choose an algorithm and implement it in shared-memory C++.  The result would be suitable for the run-time system of an enhanced version of Go, with output guards. 

The first fully distributed (non-centralized) algorithm for CSP with output guards is due to Bernstein.  Others include the work of Buckley and Silberschatz, Bagrodia, and Ramesh. All of these are message-based, and suitable for implementation across a physically distributed network: processes use an underlying (asynchronous) message-passing layer to coordinate their CSP-level synchronous communication.  In 1987, Fujimoto and Feng published an algorithm that explicitly leverages shared memory for single-machine implementations.  You could choose, for this assignment, to implement their solution.  Personally, I would probably build a shared-memory version of Bagrodia’s solution: it’s simpler and more clearly explained, and can be made very efficient. 

Detailed Requirements

You should use your solution to Assignment 1 as the base for this assignment.  To simplify testing of your code, please name your program “csp”.  As in assignment 1, please employ a Makefile to compile and link your code.  Be sure that “make clean” and “make csp” work correctly. 

When run, your program should create t threads, start them running at the same time, and arrange for each to execute roughly as follows (this is pseudocode):

    while time has not expired
        randomly select a set of k potential communication partners, S
        rendezvous(S)
        pause for u microseconds (in lieu of actual computation)

See the list of command-line arguments (below) for more on t, k, and u.  Within the rendezvous routine, a thread should arrange to communicate with exactly one of the potential partners in S.  Optionally (under control of a command-line argument; see below), before either thread returns from the rendezvous routine, each should print to stderr a log message consisting of its thread id, the thread id of its partner, and a newline.  (You will need to use a global lock on the log routine to prevent characters from different threads from interleaving.  During testing, you may find it helpful to redirect stderr to a file.) 

If your program is correct, both messages for a given rendezvous in the log will appear after the messages for any previous rendezvous of either partner and before the messages for any subsequent rendezvous of either partner.  This means that if you filter the log through grep -w i, for some thread id i, the messages for any given rendezvous should always be adjacent. 

For the purposes of the base assignment, we will not distinguish between senders and receivers; threads simply want to pair up and “communicate.”  To avoid the possibility of deadlock, with each thread waiting for communication with a set of partners none of which has mutual interest, you should arrange for thread 1 to always be willing to communicate with everyone. 

At the end of each test run, your program should calculate, for each thread i, what percentage of its rendezvous operations ended up partnering with each of its peers j∉{1, i}.  For each thread, it should then calculate the standard deviation of these percentages and the unsigned difference between the largest and smallest percentages.  Finally, it should find the largest difference and the average standard deviation across all threads, and print these two values to stderr.  If your algorithm is fair, both values should be very close to zero in a long program run. 

Given that your goal in this assignment is “merely” to generate correct behavior while permitting concurrency and potentially ensuring fairness, we will not be measuring any sort of parallel speedup.  If you are in CSC 458, however,

  1. You are required to make your algorithm fair, in the (limited) sense that no interactions tend to be prioritized over others (yes, that’s informally stated); and
  2. You are also required to ensure that the average work performed by a given thread, per rendezvous, is O(k), where k is the current number of peers with which the thread is potentially interested in communicating.

As in assignment 1, 258 students can fulfill the 458 requirements for extra credit. 

To turn in your code, follow the turnin directions.  Be sure to include a good README.pdf file.  Among other things, you’ll want to provide a narrative explanation of the pairing algorithm you chose and, if you adapted it from a message-passing algorithm in the literature, how you made it work in shared memory.  If you have questions, post to the discussion group in Blackboard

Command-line arguments

Your csp program should accept the following command-line arguments:
   -d num time to run, in seconds (default 3)
   -t num number of threads (default 16)
   -k num number of potential partners in each selection (default t/2)
   -u num μs delay between rendezvous in each thread (default 100)
   -l log each rendezvous if specified (otherwise don’t)

You may find the standard getopt library helpful to parse command-line parameters.  (Much better packages are available on the web, but getopt should suffice for this project.) 

Additional Hints

To generate pseudo-random numbers (for building sets of potential partners), I recommend the random_r library routine.  To better test your program, you may want to arrange for it to use a different “seed” for the random number generator on every run—e.g., by passing the time of day to srandom_r

To pause, a thread should call the Linux usleep function, passing the value of the -u command-line argument. 

If you choose to implement Bagrodia’s algorithm, you will want to use shared memory in lieu of underlying asynchronous messages.  I recommend a t×t array, C of “channel status” values, where C[i,j] (i ≠ j) indicates the status of communication between threads i and j.  Each value will indicate which thread currently has what Bagrodia calls the “token” and whether it has refused an interaction since receiving it.  I suggest storing the status of each thread in a separate array, so changes to the status of a given thread can be made atomically (as opposed to having to make a change to every associated channel value).  To allow you to distinguish not only between threads that are idle (looking for a partner) and threads that are active (doing something else—not looking for a partner) but also between successive instances of these states, you may want the status of a thread to be a serial number, where even means idle and odd means active.  (If the “color” [fine-grain status] of a thread needs to be visible to peers, you could use the two lowest order bits of the serial number to differentiate among the four possible colors.)  Note that if serial numbers are 64-bit numbers, they won’t overflow in your lifetime. 

You’ll want to use the alignas storage specifier in C++ to ensure that the compiler allocates employs separate cache lines for variables shared by separate sets of threads—thereby avoiding false sharing (in which threads suffer logically unnecessary cache misses because peers have modified disjoint parts of the same line). 

The possibility that threads may pause for significant time between attempted interactions means that one cannot send a “message” to a thread and be sure of a prompt reply.  In a shared-memory implementation, however, one can attempt to retract a message that has been sent to an active (non-interested) peer.  One might, for example, (1) check the status of a peer and, if it’s idle, (2) use a CAS to change the channel status of one’s communication with that peer; then (3) double-check the status of the peer.  If the peer is now active, one can try to use a CAS to restore the channel status to its previous value.  Meanwhile, it’s possible that the peer will have used a CAS to accept the message, allowing it to act.  Because both threads use CAS, you can arrange for only one to succeed, and for both to tell what happened. 

Inside your rendezvous routine, you will probably need to actively poll the status of multiple communication channels.  In an initial version of your code (or even a final version, for 258), you might poll the channels of all t−1 peers, so you can refuse interaction with peers who are not among your current potential partners.  To ensure O(k) work per rendezvous, however (as required for 458), you may need to make your current set of potential partners globally visible, so peers not in that set can avoid sending (or can retract) any messages you would otherwise need to refuse (the work of Fujimoto and Feng, mentioned above, does this.) 

If you want to read a multi-word collection of data (e.g., the state of a thread, including its potential partner set) atomically and efficiently, you may want to consider using a sequence lock (described in Section 6.2 of Shared-Memory Synchronization).  Alternatively, you could consider replacing the t×t array of channel status values with per-thread queues of incoming messages.  Each queue, of course, would itself need to be properly synchronized. 

When logging, one way to ensure that both threads log their rendezvous before either continues would be to have each perform the idle-to-active state transition for the other. 

Extra Credit Suggestions

Due Date: Tuesday, February 17, 11:59 pm.


Back to the course home page                     Last Change: 14 February 2026