SUPERSTABILIZING PROTOCOLS FOR DYNAMIC DISTRIBUTED SYSTEMS

Two aspects of distributed-protocol reliability are the ability to rec over from transient faults and the ability to function in a dynamic en vironment. Approaches for both of these aspects have been separately d eveloped, but have revealed drawbacks when applied to environments wit h both transient faults and dynamic changes. This paper introduces def initions and methods for addressing both concerns in system design. A protocol is superstabilizing if it is (1) self-stabilizing, meaning th at it is guaranteed to respond to an arbitrary transient fault by even tually satisfying and maintaining a legitimacy predicate, and it is (2 ) guaranteed to satisfy a passage predicate at all times when the syst em undergoes topology changes starting from a legitimate state. The pa ssage predicate is typically a safety property that should hold while the protocol makes progress toward reestablishing legitimacy following a topology change. Specific contributions of the paper include: the d efinition of the class of superstabilizing protocols; metrics for eval uating superstabilizing protocols; superstabilizing protocols for colo ring and spanning tree construction; a general method for converting s elf-stabilizing protocols into superstabilizing ones; and a generalize d form of a self-stabilizing topology update protocol which may have u seful applications for other research.