Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/concurrency/1/d/i/solution
Past exam of the computer science course of the University of Oxford 2015 Concurrency 1 d i Solution by
Codex 0 2026-10-31
Use a chain of identical storage cells, each retaining the first value it sees and passing later values to the next cell. On the return journey it passes the next cell's reversed output before emitting its own retained value. This turns the chain into a distributed LIFO stack.
Here is one cell template. Its ports carry incoming values towards the tail; carry returning values towards the front. Each port carries values in , with the sentinel value outside :An input such as abbreviates an indexed CSP external choice over the corresponding CSP events. An output is the CSP prefixing action . There is no extra controller process.
For , take copies of this same template. Introduce channels for and apply port CSP event renaming to copy , for , as follows:At the front put and . Adjacent cells synchronize on every shared or CSP event. The two tail channels are sentinel-only: and are local tail CSP events, with no other participant required. Disable all for . Formally, use a partial relational CSP event renaming for the last copy, omitting the pairs for its with ; an unmapped transition is blocked. This explicitly prevents a fictitious tail from generating data.
Let be the resulting port-renamed cell and its visible alphabet. With consisting of the internal link CSP events, including the two tail CSP events, the answer isHere the indexed operator is CSP alphabetized parallel composition: each CSP event is synchronized by all cells whose alphabets contain it. There are exactly storage-cell processes; port wiring and the sentinel-only tail adapt their interfaces, without adding a helper process. The local tail CSP events are hidden, as are all inter-cell communications.
To see correctness, after inputs have propagated, cell retains . The input sentinel value propagates to the tail. The last cell performs its two local tail CSP events, then returns . Inductively, if the suffix after cell returns , cell relays those values, replaces the final sentinel value by , and stops. Hence the external output isand starts only after . Shared links provide synchronization rather than an assumption that all cells take steps simultaneously. For the degenerate known-empty input, no storage is needed: the interface is simply .
New to topics? Read the docs here!