ERC Advanced Grant 339539: AOC (Adversary-Oriented Computing)

Abstract: Recent technological evolutions, including the cloud, the multicore and the social ones, are turning computing ubiquitously distributed. Yet, building high-assurance distributed programs is notoriously challenging. One of the main reasons is that these systems usually seek to achieve several goals at the same time. In short, they need to be efficient, responding effectively in various average-case conditions, as well as reliable, behaving correctly in severe, worst-case conditions. As a consequence, they typically intermingle different strategies: each to cope with some specific working condition, e.g., with or without contention, cache misses, oversizing, crashes, omissions, time-outs, malicious attacks, etc. The resulting programs end up hard to prove, verify, test and debug. Not surprisingly, there are anecdotal evidences of their fragility.

The goal of this project is to contribute to building high-assurance distributed programs by introducing a new dimension for separating their concerns, as well as a matching scheme for modularly composing them within the same program. In short, the project will explore the inherent power and limitations of a novel paradigm, Adversary-Oriented Computing (AOC), according to which a distributed program is built in an incremental manner. Sub-programs, each implementing a specific strategy to cope with a given adversary (modeling a specific working condition), are designed, proved, verified, implemented, tested and debugged independently. They are then composed, possibly dynamically, as black-boxes within the same global program.

The AOC project is ambitious and it seeks to fundamentally revisit the way distributed algorithms are designed and distributed systems are implemented. The gain expected in comparison with todays’s approaches is substantial, and actually proportionnal to the degree of complexity of the distributed problem at hand. A proof of concept of the feasibility of the AOC paradigm has already been conducted on a non-trivial case. This preliminary phase emphasized the very fact that the modularity obtained with AOC does not necessarily hamper efficiency, while significantly improving assurance. It also highlighted two principles underyling AOC: progressive abortability and reduction to the strongest adversary. Both principles appear general enough to be applicable to the wide variety of research chapters considered in this project.