Content-based publish/subscribe overlays oÂ®er a scalable mes- saging substrate for various event-based distributed systems. In an enter- prise environment where service level agreements are strictly enforced, maintaining high availability of the broker overlay is critical. To meet this requirement, protocols are developed to replace or load-balance a broker that misbehaves|perhaps due to failure, congestion, or peri- odic maintenance|with a new broker in a running system. The key to our techniques is distributed replication of routing information on an adaptively deployed new broker which serves reliable re-route or alter- native paths for publication messages. Our techniques focuses on avoid- ing lengthy disruption of messaging service, and supporting consistency properties on publication delivery via the replica.