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
fDate :
5/1/1995 12:00:00 AM
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;
Journal_Title :
Software Engineering, IEEE Transactions on
