About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
PODC 1993
Conference paper
Bounded round numbers
Abstract
This paper presents a systematic, modular technique for transforming a large class of unbounded shared-memory algorithms into bounded algorithms. We show that any unbounded algorithm based on a certain asynchronous rounds structure can be `compiled' into a bounded algorithm in a way that preserves correctness and running time. As evidence that the asynchronous rounds structure is natural for wait-free algorithms, we identify a number of unbounded algorithms in the literature to which our transformation can either be applied directly, or applied after minor modifications. The running times of the resulting algorithms match these of their unbounded counterparts and hence in most cases the resulting algorithms are faster than any other known bounded solutions to the corresponding problems. In particular, we get a bounded consensus algorithm whose running time is O(n log2 n) and a bounded snapshot scan algorithm whose running time is O(n log n).