On the cost of composing shared-memory algorithms
Dan Alistarh, Rachid Guerraoui, Petr Kuznetsov, Giuliano Losa · 2012
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.