The subject matter of this specification can be implemented in, among other things, a method that includes establishing first federation links between a message broker system and neighbors of the message broker system. The method further includes distributing information describing the first federation links to other message broker systems. The method further includes receiving information describing second federation links between each of the other message broker systems and neighbors of each of the other message broker system. The method further includes identifying shortest paths between the message broker system and each of the other message broker systems. The method further includes receiving a request to send a message from a source message broker system to a destination message broker system. The method further includes determining that none of the shortest paths to the destination message broker system are available and, in response, taking corrective action.