Technical Report Number
A useful way to design simple and robust protocols is to make them self-stabilitizing. We describe a simple technique for self-stabilization called counter flushign which is applicable to a number of distributed algorithms. A randomized version of counter flushing is shown to have extremely small expected stabilization time. We show how our technique helps to crisply understand and improve some previous distributed algorithms. Then we apply it to a variety of total algorithms for deadlock detection, propagation of information with feedback, resets and snapshots. Our stabilizing snapshot protocol has much better complexity than the previous stabilizing non-blocking snapshot protocol. Hence it can be used to improve the complexity of general compilers that convert arbitrary asynchronous protocols into stabilizing equivalents.
Varghese, George, "Self-stabilization by Counter Flushing" Report Number: WUCS-94-14 (1994). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7DJ5CWK