RESOURCE BOUNDS FOR SELF-STABILIZING MESSAGE-DRIVEN PROTOCOLS

Self-stabilizing message-driven protocols are defined and discussed. T he class weak exclusion that contains many natural tasks such as l-exc lusion and token passing is defined, and it is shown that in any execu tion of any self-stabilizing protocol for a task in this class, the co nfiguration size must grow at least in a logarithmic rate. This last l ower bound is valid even if the system is supported by a time-out mech anism that prevents communication deadlocks. Then we present three sel f-stabilizing message-driven protocols for token passing. The rate of growth of configuration size for all three protocols matches the afore mentioned lower bound. Our protocols are presented for two-processor s ystems but can be easily adapted to rings of arbitrary size. Our resul ts have an interesting interpretation in terms of automata theory.