DocumentCode
786003
Title
Analyzing expected time by scheduler-luck games
Author
Dolev, Shlomi ; Israeli, Amos ; Moran, Shlomo
Author_Institution
Dept. of Math. & Comput. Sci., Ben-Gurion Univ. of the Negev, Beer-Sheva, Israel
Volume
21
Issue
5
fYear
1995
fDate
5/1/1995 12:00:00 AM
Firstpage
429
Lastpage
439
Abstract
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
computational complexity; distributed processing; game theory; processor scheduling; protocols; random processes; scheduling; software performance evaluation; expected time analysis; leader election; performance analysis; processor; randomized distributed protocols; read/write atomicity; scheduler-luck games; uniform self-stabilizing protocols; Atomic measurements; Computer science; Distributed algorithms; Helium; Nominations and elections; Performance analysis; Processor scheduling; Protocols; Tail; Time measurement;
fLanguage
English
Journal_Title
Software Engineering, IEEE Transactions on
Publisher
ieee
ISSN
0098-5589
Type
jour
DOI
10.1109/32.387472
Filename
387472
Link To Document