Resource bounds for self stabilizing message driven protocols

Abstract. Self-stabilizing message-driven protocols are defined and discussed. The class weak exclusion that contains many natural tasks such as ℓ-exclusion and token passing is defined, and it is shown that in any execution of any self-stabilizing protocol for a task in this class, the configuration size must grow at least in a logarithmic rate. This last lower bound,is valid even if the system is supported by a time-out mechanism,that prevents communication,deadlocks. Then we present three self-stabilizing message-driven protocols for token passing. The rate of growth of configuration size for all three protocols matches the aforementioned lower bound. Our protocols are presented for two-processor systems but can be easily adapted to rings of arbitrary size. Our results have an interesting interpretation in terms of automata,theory. Key words. self-stabilization, message passing, token passing, shared memory AMS subject classifications. 68M10, 68M15, 68Q10, 68Q20 PII. S0097539792235074