Automatic Verification of Linearization Policies

Conférence
 - 
VERIMAG
Parosch Aziz ABDULLA
Jeudi 29 septembre 2016
Réalisation technique : Antoine Orlandi | Tous droits réservés

We consider the problem of proving linearizability for concurrent threads that access a shared data structure. Such systems give rise to unbounded numbers of threads that operate on an bounded data domain and that access dynamically allocated memory. Furthermore, proving linearizability is harder than proving control state reachability due to existentially quantified linearization points. The problem is further complicated by the presence of advanced features such as non-fixed linearization points, speculation, and helping. In this presentation, we present a framework that can automatically verify linearizability for concurrent data structures that implement sets, stacks, and queues. We use a specification formalism for linearization techniques which allows the user to specify, in a simple and and concise manner, complex patterns including non-fixed linearization points. Then, we define abstraction techniques that allow to make the size of the data domain and the number of threads finite.

L'UMS MI2S a fermé le 31 décembre 2016, les vidéos hébergées sur son site le sont maintenant sur le site de GRICAD. Conformément à la loi informatique et libertés du 6 janvier 1978 modifiée, vous pouvez exercer vos droits de rétraction ou de modification relatifs aux autorisations validées par MI2S auprès de l'UMS GRICAD.