Self-stabilizing strong fairness under weak fairness

Fairness assumptions have a great impact on distributed algorithms. They play a major role in determining the time complexity and the correctness of algorithms, since progress or freedom from various types of starvation may not be guaranteed without fairness assumptions. In this paper, we present a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2001-04, Vol.12 (4), p.337-345
Main Author: Karaata, M.H.
Format: Article
Language:English
Subjects:
Algorithms
Broadcasting
Complexity
Computer networks
Concurrency
Concurrent computing
Distributed algorithms
Multiaccess communication
Protocols
Time optimal
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Fairness assumptions have a great impact on distributed algorithms. They play a major role in determining the time complexity and the correctness of algorithms, since progress or freedom from various types of starvation may not be guaranteed without fairness assumptions. In this paper, we present a stabilizing deterministic algorithm allowing simultaneous execution of actions for strong fairness under weak fairness assumption, in addition, we show that the proposed algorithm yields a high degree of concurrency. We conclude the paper with some remarks on issues such as time optimal implementation of strong fairness and open problems related to fairness.
ISSN:1045-9219
1558-2183
DOI:10.1109/71.920585