We consider the problem of synchronizing prioritized data on two distinct hosts in disruption-tolerant networks (DTNs). To this effect, we propose and analyze a new interactive protocol for priority-oriented synchronization, called P-CPI, that is especially efficient in terms of bandwidth usage. This middleware protocol has features that are particularly useful for DTN routing in constrained or tactical environments, including (i) communication and computational complexity primarily tied to the number of differences between the hosts rather than the amount of the data overall and (ii) a memoryless fast restart after interruption. We provide a novel analysis of this protocol, substantiating a high-probability performance bound and memoryless fast-restart in logarithmic time. As a proof of concept, we demonstrate improved delivery rate and reduced metadata and average delay in a DARPA-supported DTN routing application called RAPID.