Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-14.PDF

Technical Report Number

WUCS-94-14

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7DJ5CWK

Download

Share

COinS