Self-stabilizing Routing in Publish-Subscribe Systems

Shen, Zhenhui and Tirthapura, Srikanta (2004) Self-stabilizing Routing in Publish-Subscribe Systems. Publisher UNSPECIFIED.

This is the latest version of this eprint.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

We show how to build fault-tolerant publish-subscribe systems by making them self-stabilizing. Neighboring message routers (or brokers) periodically exchange state about their routing tables, and take corrective actions if (and only when) necessary. We prove that the resulting algorithm brings the system back to a legal global state if it starts out in a faulty state. We further improve the efficiency of our self-stabilizing algorithm in two directions: (1)We show how to reduce the size of the stabilization messages by having the routers exchange only ''sketches'' of routing tables which are much smaller than the routing tables themselves. These sketches are based on Bloom filters, but we provide a new accuracy/space tradeoff. (2)The self-stabilization procedure, though correct in all cases, may not lead to the most efficient recovery from every fault. One such special case is a transient edge failure. For this important special case, we optimize the self-stabilization so that the message complexity for recovery is at most twice the cost of an ''optimal'' protocol to recover from such a fault. Our simulations suggest that both the above produce significant improvements in the efficiency of the protocol.

Available Versions of this Item

• Self-stabilizing Routing in Publish-Subscribe Systems (deposited 27 May 2004) [Currently Displayed]

Archive Staff Only: edit this record