Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability
Journal
Theoretical Computer Science
Journal Volume
243
Journal Issue
1-2
Pages
307-338
Date Issued
2000
Author(s)
Abstract
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. © 2000 Elsevier Science B.V. All rights reserved.
Subjects
Multiparty interaction; Randomized algorithm; Strong interaction fairness; Weak interaction fairness
Type
journal article