Certain example embodiments described herein relate to techniques for propagating changes across broker territories. Broker territories are formed from broker servers that are placed in different geographical locations. When a territory is formed, a minimum spanning tree (MST) is formed between the brokers in the territory and, as a result, every broker in the territory will know its nearest neighbors and will be able to propagate the changes to these brokers. The MST may be dynamic in certain example embodiments. Each broker may be configured to calculate the cost of the edges based on certain predefined parameters, e.g., in computing the MSTs. Parameters that may be used in determining edge weights may include, for example, response to ping, geographical distance, whether a broker is in a LAN versus in a WAN, whether brokers are embedded in a mobile device, predefined categories (e.g., based on device type, etc.), and/or the like.