Content-based publish/subscribe overlays offer a scalable messaging substrate for various event-based distributed systems. In an enterprise 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 a broker that misbehavesâ€”perhaps due to failure, congestion, or periodic maintenanceâ€”with a new broker in a running system. The key to our replacement technique is distributed replication of routing information on an adaptively deployed new broker which serves reliable re-route paths for publication messages. Our technique focuses on avoiding lengthy disruption of messaging service, and supporting best-effort weak consistency on publication delivery via the replica.