The aim of this work is to define a planner that enables robust legged locomotion for complex multi-agent systems consisting of several holonomically constrained quadrupeds. To this end, we employ a methodology based on behavioral systems theory to model the sophisticated and high-dimensional structure induced by the holonomic constraints. The resulting model is then used in tandem with distributed control techniques such that the computational burden is shared across agents while the coupling between agents is preserved. Finally, this distributed model is framed in the context of a predictive controller, resulting in a robustly stable method for trajectory planning. This methodology is tested in simulation with up to five agents and is further experimentally validated on three A1 quadrupedal robots subject to various uncertainties, including payloads, rough terrain, and push disturbances.