--- res: bibo_abstract: - Decades of research in distributed computing have led to a variety of perspectives on what it means for a concurrent algorithm to be efficient, depending on model assumptions, progress guarantees, and complexity metrics. It is therefore natural to ask whether one could compose algorithms that perform efficiently under different conditions, so that the composition preserves the performance of the original components when their conditions are met. In this paper, we evaluate the cost of composing shared-memory algorithms. First, we formally define the notion of safely composable algorithms and we show that every sequential type has a safely composable implementation, as long as enough state is transferred between modules. Since such generic implementations are inherently expensive, we present a more general light-weight specification that allows the designer to transfer very little state between modules, by taking advantage of the semantics of the implemented object. Using this framework, we implement a composed longlived test-and-set object, with the property that each of its modules is asymptotically optimal with respect to the progress condition it ensures, while the entire implementation only uses objects with consensus number at most two. Thus, we show that the overhead of composition can be negligible in the case of some important shared-memory abstractions.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Dan-Adrian foaf_name: Alistarh, Dan-Adrian foaf_surname: Alistarh foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-3650-940X - foaf_Person: foaf_givenName: Rachid foaf_name: Guerraoui, Rachid foaf_surname: Guerraoui - foaf_Person: foaf_givenName: Petr foaf_name: Kuznetsov, Petr foaf_surname: Kuznetsov - foaf_Person: foaf_givenName: Giuliano foaf_name: Losa, Giuliano foaf_surname: Losa bibo_doi: 10.1145/2312005.2312057 dct_date: 2012^xs_gYear dct_language: eng dct_publisher: ACM@ dct_title: On the cost of composing shared-memory algorithms@ ...