Trade-offs in Token Ring Systems

In addition to trade-offs between convergence and response spans as described by Gouda and Evangelist, we consider state space utilization with regard to processing and communications, and sensitivity to delay time estimates. In order to be delay insensitive, estimates of transmission and/or computation time are used, which we implement as virtual nodes. The estimated number of nodes is defined as N_E. We define M as the number of processes, and N as the total number of nodes required in the problem space. These algorithms require that N_E >; N in order that correctness and desired behavior can be guaranteed. We define auto-synchronization as the characteristic of a system such that performance is related to N, rather than N_E, even though state space necessarily is related to N_E. Although our examples are delay insensitive deterministic unidirectional token rings, we believe that these concepts apply to many other paradigms of self-stabilization.