ANALYZING EXPECTED TIME BY SCHEDULER-LUCK GAMES

In this paper we introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the perform ance of randomized distri buted protocols. We apply it in studying uniform self-stabilizing prot ocols for leader election under read/write atomicity. We present two p rotocols for the case where each processor in the system can communica te with all other processors and analyze their performance using the s l-game technique.