Analyzing expected time by scheduler-luck games
- 1 May 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 21 (5) , 429-439
- https://doi.org/10.1109/32.387472
Abstract
In this paper we introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique.Keywords
This publication has 23 references indexed in Scilit:
- Uniform dynamic self-stabilizing leader electionIEEE Transactions on Parallel and Distributed Systems, 1997
- Self-stabilization of dynamic systems assuming only read/write atomicityDistributed Computing, 1993
- Wait-free clock synchronizationPublished by Association for Computing Machinery (ACM) ,1993
- Self-stabilizing ring orientationPublished by Springer Nature ,1991
- Symmetry breaking in distributed networksInformation and Computation, 1990
- Token management schemes and random walks yield self-stabilizing mutual exclusionPublished by Association for Computing Machinery (ACM) ,1990
- A modular technique for the design of efficient distributed leader finding algorithmsACM Transactions on Programming Languages and Systems, 1990
- A Simple and Efficient Randomized Byzantine Agreement AlgorithmIEEE Transactions on Software Engineering, 1985
- Selecting a leader in a clique in 0(N log N) messagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974