@inproceedings{8012,
  abstract     = {Asynchronous programs are notoriously difficult to reason about because they spawn computation tasks which take effect asynchronously in a nondeterministic way. Devising inductive invariants for such programs requires understanding and stating complex relationships between an unbounded number of computation tasks in arbitrarily long executions. In this paper, we introduce inductive sequentialization, a new proof rule that sidesteps this complexity via a sequential reduction, a sequential program that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. We have implemented and integrated our proof rule in the CIVL verifier, allowing us to provably derive fine-grained implementations of asynchronous programs. We have successfully applied our proof rule to a diverse set of message-passing protocols, including leader election protocols, two-phase commit, and Paxos.},
  author       = {Kragl, Bernhard and Enea, Constantin and Henzinger, Thomas A and Mutluergil, Suha Orhun and Qadeer, Shaz},
  booktitle    = {Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation},
  isbn         = {9781450376136},
  location     = {London, United Kingdom},
  pages        = {227--242},
  publisher    = {Association for Computing Machinery},
  title        = {{Inductive sequentialization of asynchronous programs}},
  doi          = {10.1145/3385412.3385980},
  year         = {2020},
}

@inproceedings{8089,
  abstract     = {We consider the classical problem of invariant generation for programs with polynomial assignments and focus on synthesizing invariants that are a conjunction of strict polynomial inequalities. We present a sound and semi-complete method based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize positive polynomials over a semi-algebraic set.

On the theoretical side, the worst-case complexity of our approach is subexponential, whereas the worst-case complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential. Even when restricted to linear invariants, the best previous complexity for complete invariant generation is exponential (Colon et al, CAV 2003). On the practical side, we reduce the invariant generation problem to quadratic programming (QCLP), which is a classical optimization problem with many industrial solvers. We demonstrate the applicability of our approach by providing experimental results on several academic benchmarks. To the best of our knowledge, the only previous invariant generation method that provides completeness guarantees for invariants consisting of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination and cannot even handle toy programs such as our running example.},
  author       = {Chatterjee, Krishnendu and Fu, Hongfei and Goharshady, Amir Kafshdar and Goharshady, Ehsan Kafshdar},
  booktitle    = {Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation},
  isbn         = {9781450376136},
  location     = {London, United Kingdom},
  pages        = {672--687},
  publisher    = {Association for Computing Machinery},
  title        = {{Polynomial invariant generation for non-deterministic recursive programs}},
  doi          = {10.1145/3385412.3385969},
  year         = {2020},
}