Home » forums » LtU Forum

Concurrency and dominators

Hi all,

I noticed a similarity between semaphores and other thread-synchronization mechanisms, and control dominators (from control flow theory).

A control dominator is a node that controls the control paths that go through it. Basically, in a control flow graph, if node B post-dominates node A, any path from A to the end-node *must* go through B.

In a similar way, a semaphore guarantees that any path from the wait() call to the end of the execution, *must* go through the signal() call. This feels like "runtime" post-dominance, which is of course a very informal way of putting it.

Does anybody know if there is more research about this similarity? Can dominance be generalized to a runtime concept? Can it help us understand thread-based concurrency better, or is that a lost cause in advance?

By Koen Van Damme at 2006-12-14 13:11 | LtU Forum | previous forum topic | next forum topic | other blogs | 5678 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Linearity, continuations & post-dominators

I (along with Andrew Myers) observed in a paper I wrote in 1999 ("Secure Information Flow and CPS") that linear continuations are the dynamic counterpart of a post-dominator. A linear continuation is one that is guaranteed to be invoked at some point in the future--so all control flow must eventually pass through it. In a later paper ("Observational Determinism for Concurrent Program Security"), we used a similar idea for "linear join patterns" to specify the merge points (synchronization points) of a concurrent program.

The context of those papers was information-flow security, and I've been meaning to go back to investigate more uses of linearity in concurrent settings.

By Steve Zdancewic at Tue, 2006-12-19 04:52 | login or register to post comments

Thanks!

Looks very interesting after a first quick scan. I'll make time over the weekend to go through it in detail. Thanks for sharing this.

By Koen Van Damme at Thu, 2006-12-21 08:16 | login or register to post comments