Self-stabilizing Routing in Publish-Subscribe Systems Zhenhui Shen and Srikanta Tirthapura   View Paper (PDF)   Return to Routing over Peer-to-Peer Networks Abstract Publish Subscribe Systems route events to interested subscribers through a distributed network of routing tables. We present a self-stabilizing algorithm that maintains these routing tables in a consistent distributed state, and recovers from faults in the network. Neighboring message routers (or brokers) periodically exchange their routing table state, and take corrective actions if (and only when) necessary. We formally prove that the resulting algorithm brings the system back to a legal global state if it starts out in a faulty state. Further, we show how to reduce the size of the periodic message exchanges by exchanging sketches of the routing tables which are much smaller than the routing tables themselves. We present a message size/accuracy tradeoff of using these sketches, which are based on Bloom filters. We have simulated our algorithm, and present our results of studying the important special case of a transient edge failure in greater detail. ©2005 Association for Computing Machinery