The Assignment Problem

Abstract : In the allocation problem, asynchronous processors must partition a set of items so that each processor leave knowing all items exclusively allocated to it. We introduce a new variant of the allocation problem called the assignment problem, in which processors might leave having only partial knowledge of their assigned items. The missing items in a processor's assignment must eventually be announced by other processors. While allocation has consensus power 2, we show that the assignment problem is solvable read-write wait-free when k processors compete for at least 2k − 1 items. Moreover, we propose a long-lived read-write wait-free assignment algorithm which is fair, allocating no more than 2 items per processor, and in which a slow processor may delay the assignment of at most n items, where n is the number of processors. The assignment problem and its read-write solution may be of practical interest for implementing resource allocators and work queues, which are pervasive concurrent programming patterns, as well as stream-processing systems.
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01955902
Contributor : Carole Delporte-Gallet <>
Submitted on : Friday, December 14, 2018 - 4:41:17 PM
Last modification on : Wednesday, August 7, 2019 - 12:14:40 PM
Long-term archiving on : Friday, March 15, 2019 - 5:37:17 PM

File

final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01955902, version 1

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Giuliano Losa. The Assignment Problem. International Conference on Distributed Computing and Networking, , 2018, Varanasi, India. ⟨hal-01955902⟩

Share

Metrics

Record views

55

Files downloads

58