VSComp 2014

Broader Scope, Sharper Criteria

After the initial editions established the competition's format, VSComp 2014 significantly broadened the range of verification domains represented in the problem set. Where earlier editions focused primarily on sequential algorithm correctness and data-structure invariants, the 2014 problems introduced concurrent data structures, behavioural refinement, and protocol-level reasoning. This expansion reflected the growing capabilities of verification tools and the formal methods community's increasing confidence that concurrency and refinement were tractable targets for machine-checked proof.

Organisers included members drawn from the formal methods research community. The evaluation criteria became more explicit than in preceding years: reviewers assessed not only whether a proof was mechanically valid, but also whether the specification was complete and whether the submission was documented clearly enough for independent assessment. These three pillars — correctness, completeness, and clarity — are described in detail on the rules page.

The competition took place over an approximately 24-hour submission window on 14–15 June 2014. Participants could use any verification tool or proof assistant, consistent with the tool-agnostic policy that has characterised every edition of VSComp. Solutions were submitted electronically and evaluated by the organising committee.

What the 2014 Edition Covered

The five problems spanned four broad verification domains: concurrency, refinement, functional correctness, and protocol/state-machine reasoning. Two problems (P1-2014 and P3-2014) dealt directly with concurrent data structures — a lock-free queue and a monotonic counter — requiring participants to reason about atomicity, memory ordering, and thread interference. These were among the hardest problems ever posed in a VSComp edition.

Refinement problems (P2-2014 and P5-2014) asked participants to show a formal correspondence between abstract specifications and concrete implementations. This is a different style of verification from assertional reasoning: rather than proving that a loop preserves an invariant, the participant must construct a simulation relation or bisimulation and show that every behaviour of the concrete system is permitted by the abstract one.

The remaining problem (P4-2014) returned to classical functional correctness — verifying a priority queue — but at a level of rigour that required careful treatment of the heap property and extraction semantics. Together, the problem set tested a wider range of verification skills than any previous edition. For a cross-year comparison, consult the problems catalogue.

How Submissions Worked

The submission window for VSComp 2014 was approximately 24 hours, opening on 14 June and closing on 15 June 2014. During this period, participants prepared their solutions and submitted them through the competition's designated channels. The compressed timeframe was a deliberate design choice: it tested not only verification skill but also the practical usability of the tools themselves. Could a participant specify, implement, annotate, and verify a non-trivial program within a single day?

Submissions were expected to include three components: annotated source code with embedded specifications, the proof artifacts generated by the participant's tool of choice, and a written explanation of the verification strategy. This last component — the strategy document — was new relative to the earliest editions and reflected a growing recognition that a proof is only useful if others can understand and reproduce it.

The evaluation committee assessed entries against the published criteria. Partial solutions were accepted: a submission that verified three of five problems, or that proved correctness but not completeness for a given problem, still received credit proportional to its coverage. Full evaluation details are on the rules page.

2014 Problem Set

Five problems were published for the 2014 edition. Each card below provides a summary; detailed descriptions are available in the problems catalogue.

Submitted Solutions

Solutions submitted for the 2014 problems are collected in the solutions archive. The expanded scope of this edition meant that submissions drew on a particularly diverse set of tools. Concurrency problems attracted entries using specialised concurrent separation logic frameworks, while the refinement problems saw contributions from teams using TLA+, Event-B, and similar specification languages.

The 24-hour window also influenced the character of submissions. Some participants focused depth-first, producing thorough solutions for one or two problems rather than attempting all five. Others aimed for breadth, submitting partial proofs across the full set. Both strategies were valid under the evaluation criteria; the solutions page reflects this variety.

Competition Artifacts

The following artifacts are associated with the 2014 edition. Where original documents remain available, they are provided below. Some historical materials are provided as-is; where unavailable, we summarise the format.

Errata and Clarifications

During the 24-hour submission window, the organisers issued several clarifications in response to participant questions. The most common queries concerned the concurrency problems: what memory model should be assumed for the lock-free queue (P1-2014), and whether the monotonic counter (P3-2014) needed to handle overflow. The organisers clarified that participants should state their assumptions explicitly and that reasonable assumptions would be accepted provided they were documented.

The refinement mapping problem (P2-2014) prompted a minor clarification regarding whether participants were required to show a forward simulation, a backward simulation, or either. The organisers confirmed that either direction was acceptable, as long as the chosen approach was sound and the proof was complete.

No corrections to the problem statements were necessary after the competition concluded. For context on how later editions handled errata, see the 2015 and 2017 year hubs.

The Verification Landscape in 2014

By 2014, the formal methods landscape had shifted considerably from the inaugural 2010 edition. SMT solvers were faster and more capable, concurrent separation logic had matured from a theoretical framework into a practical tool, and refinement-based development methods had gained traction in both academia and select industrial settings. The 2014 problem set was designed to test these advances directly.

The inclusion of concurrency problems was particularly significant. In 2010, reasoning about concurrent programs with machine-checked proofs was largely the province of specialist research groups. By 2014, tools supporting concurrent reasoning had become accessible enough that a competition problem was feasible — challenging, certainly, but not out of reach for a well-prepared participant with a suitable tool.

The history page provides a broader timeline of formal methods events, and the publications page lists academic work that discusses the 2014 competition and its outcomes.