We introduce abortable and query-abortable object types intended for implementation in asynchronous shared-memory systems with low contention. Implementations of such types behave like ordinary objects when accessed sequentially, but may abort operations when accessed concurrently. An aborted operation may or may not take effect, i.e., cause a state transition, and it returns no indication of which possibility occurred. Since this uncertainty can be problematic, a query-abortable type supports a QUERY operation that each process can use to determine its last non-QUERY operation on the object that caused a state transition, and the response associated with this state transition. Our research is closely related to obstruction-free implementations (introduced by Herlihy, Luchangco and Moir) and responsive obstruction-free implementations (introduced by Attiya, Guerraoui and Kouznetsov). Like abortable and query-abortable types, these implementations may exhibit degraded behaviour in the face of contention. We show that abortable registers--registers strictly weaker than safe registers--can be used to obtain obstruction-free and responsive obstruction-free implementations for any type. We present universal constructions for abortable and query-abortable types that are novel and efficient in the number of registers used. Specifically, they are based on a simple timestamping mechanism for detecting concurrent executions, and, in systems with n processes, use only n abortable registers or only O(n^2) single-reader, single-writer abortable registers. The timestamping mechanism we introduce is based on the inc&read counter type and appears to be interesting in its own right. As a generalization, we study the k-inc&read counter types, for k>0. We also identify a potential problem with correctness properties based on step contention: with such properties, the composition of correct object implementations may result in an implementation that is not correct. In other words, implementations defined in terms of step contention are not always composable. To avoid this problem, we introduce a property based on interval contention, namely non-triviality, to define the correct behaviour of abortable and query-abortable object implementations.

We introduce abortable and query-abortable object types intended for implementation in asynchronous shared-memory systems with low contention. Implementations of such types behave like ordinary objects when accessed sequentially, but may abort operations when accessed concurrently. An aborted operation may or may not take effect, i.e., cause a state transition, and it returns no indication of which possibility occurred. Since this uncertainty can be problematic, a query-abortable type supports a QUERY operation that each process can use to determine its last non-QUERY operation on the object that caused a state transition, and the response associated with this state transition. Our research is closely related to obstruction-free implementations (introduced by Herlihy, Luchangco and Moir) and responsive obstruction-free implementations (introduced by Attiya, Guerraoui and Kouznetsov). Like abortable and query-abortable types, these implementations may exhibit degraded behaviour in the face of contention. We show that abortable registers--registers strictly weaker than safe registers--can be used to obtain obstruction-free and responsive obstruction-free implementations for any type. We present universal constructions for abortable and query-abortable types that are novel and efficient in the number of registers used. Specifically, they are based on a simple timestamping mechanism for detecting concurrent executions, and, in systems with n processes, use only n abortable registers or only O(n^2) single-reader, single-writer abortable registers. The timestamping mechanism we introduce is based on the inc&read counter type and appears to be interesting in its own right. As a generalization, we study the k-inc&read counter types, for k>0. We also identify a potential problem with correctness properties based on step contention: with such properties, the composition of correct object implementations may result in an implementation that is not correct. In other words, implementations defined in terms of step contention are not always composable. To avoid this problem, we introduce a property based on interval contention, namely non-triviality, to define the correct behaviour of abortable and query-abortable object implementations.

Dans un ordinateur multiprocesseur, lors de l'accès à la mémoire partagée, il faut synchroniser les entités de calcul (processus). Cela peut se faire à l'aide de verrous, mais des problèmes se posent (par exemple interblocages, mauvaise tolérance aux pannes). On s'est intéressé à l'implémentation d'abstractions (consensus et construction universelle) qui peuvent faciliter la programmation concurrente sans attente, sans utiliser de verrous mais basés sur des lectures/écritures atomiques (LEA). L'usage exclusive des LEA ne permet pas de réaliser un consensus sans attente. Néanmoins, autoriser l'usage de primitives offrant une puissance de synchronisation plus forte que des LEA, mais coûteuse en temps de calcul, le permet. Nous nous sommes donc intéressés dans cette thèse à des programmes qui limitent l'usage de ces primitives aux seules situations où les processus sont en concurrence, ces programmes sont dit solo-rapides. Une autre piste étudiée est de permettre à l'objet, lorsqu'il y a de la concurrence, de retourner une réponse spéciale "abandon" qui signifie l'abandon des calculs en cours. Ces objets sont dit abandonnables. D'une part, nous donnons des implémentations d'objets concurrents sans attente, abandonnables et/ou solo-rapides. Pour cela, nous proposons une construction universelle qui assure à l'objet implémenté d'être abandonnable et solo-rapide ; nous avons réalisés des algorithmes de consensus solo-rapides et des algorithmes de consensus abandonnable. D'autre part nous étudions la complexité en espace de ces implémentations en proposant des bornes inférieures sur l'implémentation des objets abandonnables et sur le consensus. / In multiprocessor computer, synchronizations between processes are needed for the access to the shared memory. Usually this is done by using locks, but there are some issues as deadlocks or lack of fault-tolerance. We are interested in implementing abstractions (as consensus or universal construction) which ease the programming of wait-free concurrent objects, without using lock but based on atomic Read/Write operations (ARW). Only using the ARW does not permit to implement wait-free consensus. The use of primitives which offer a higher power of synchronization than the ARW is needed. But these primitives are more expensive in computing time. Therefore, we are interested in this thesis in the design of algorithms which restrict the use of these primitives only to the cases where processes are in contention. These algorithms are said solo-fast. Another direction is to allow the object to abort the computation in progress - and to return a special response "abort" - when there is contention. These objects are named abortable. On the one hand we give wait-free, abortable and/or solo-fast concurrent object implementations. Indeed we proposed a universal construction which ensure to the implemented object to be abortable and solo-fast. We have also realized solo-fast consensus algorithms and abortable consensus algorithms. On the other hand, we study the space complexity of these implementations : we prove space lower bound on the implementation of abortable object and consensus.