Dynamic Deadlock Verification for General Barrier Synchronisation

Tiago Cogumbreiro, Raymond Hu, Francisco Martins, Nobuko Yoshida

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)


    We present Armus, a verification tool for dynamically detecting or avoiding barrier deadlocks. The core design of Armus is based on phasers, a generalisation of barriers that supports split-phase synchronisation, dynamic
    membership, and optional-waits. This allows Armus to handle the key barrier synchronisation patterns found in modern languages and libraries. We implement Armus for X10 and Java, giving the first sound and complete barrier deadlock verification tools in these settings.

    Armus introduces a novel event-based graph model of barrier concurrency constraints that distinguishes task-event and event-task dependencies. Decoupling these two kinds of dependencies facilitates the verification of distributed barriers with dynamic membership, a challenging feature of X10. Further, our base graph representation can be dynamically switched between a task-to-task model, Wait-for Graph (WFG), and an event-to-event model, State
    Graph (SG), to improve the scalability of the analysis.

    Formally, we show that the verification is sound and complete with respect to the occurrence of deadlock in our core phaser language; and that switching graph representations preserves the soundness and completeness properties.
    These results are machine checked with the Coq proof assistant. Practically, we evaluate the runtime overhead of our implementations using three benchmark suites in local and distributed scenarios. Regarding deadlock detection,
    distributed scenarios show negligible overheads and local scenarios show overheads below 1.15×. Deadlock avoidance is more demanding, and highlights the potential gains from dynamic graph selection. In one benchmark
    scenario, the runtime overheads vary from: 1.8× for dynamic selection, 2.6× for SG-static selection, and 5.9× for WFG-static selection.
    Original languageEnglish
    Article number1
    Pages (from-to)1-38
    Number of pages38
    JournalACM Letters on Programming Languages and Systems (TOPLAS)
    Issue number1
    Early online date1 Dec 2018
    Publication statusPublished - 1 Mar 2019


    • Barrier synchronisation
    • Phasers
    • Deadlock detection
    • Deadlock avoidance
    • X10
    • Java


    Dive into the research topics of 'Dynamic Deadlock Verification for General Barrier Synchronisation'. Together they form a unique fingerprint.

    Cite this