Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability

摘要

We present two randomized algorithms, one for message passing and the other for shared memory, that, with probability 1, schedule multiparty interactions in a strongly fair manner. Both algorithms improve upon a previous result by Joung and Smolka (proposed in a shared-memory model, along with a straightforward conversion to the message-passing paradigm) in the following aspects: first, processes' speeds as well as communication delays need not be bounded by any predetermined constant. Secondly, our algorithms are completely decentralized, and the shared-memory solution makes use of only single-writer variables. Finally, both algorithms are symmetric in the sense that all processes execute the same code, and no unique identifier is used to distinguish processes. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 34]