A wait-free sorting algorithm
Nir Shavit, Eli Upfal, Asaph Zemach · 1997
Sorting in one of a set of fundamental problems in computer saence.In this paper we present the first wait-free algorithm for sorting an input array of size N using P s N proceseom to achieve optimal running time.Known sorting algorithms, when made wait-flee through previously eskabliehed trsmsformation techniques have complexity O(logs N).The randomized algorithm we present here, when run in the CRCW PRAM model executes in optimal O(log N) time where P = N and O(N log N/P) otherwise.The wait-free property guarantees that the sort will complete despite any delays or failures incumed by the processors.This is a very desirable property from an operating systems point of view, since it allows oblivious thread scheduling as well as thread creation and deletion, without fear of losing the algorithm's correctness.We further present a variant of the algorithm which is shown to suffer no more than O(m) cent ention when rust Sy'tlChrOnOUd~.Sorting is a basic algorithmic building block and hm attracted the attention of many reeearchera.In this paper we present a wait-i%ee algorithm for sorting an ssmay of N elements, in the CRCW PRAM model with processor failures and undetectable restarts.Herlihy [17] defines a wait-free data structure M one on which any operation by any processor is guaranteed to complete within a bounded number of steps, regardless of the actions or failures of other proceesom.By extension, a wait-free algorithm for some iixed-size problem is guaranteed to arrive at the solution within a bounded "MIT and