White spaces promise to revolutionize the way wireless connectivity is delivered over wide areas. However, large-scale white space networks face the problem of allocating channels to multiple contending users in the wide white space band. To tackle the issue, we first examine wireless propagation in a long-distance outdoor white space testbed and find that a complex combination of free-space loss and antenna effects impacts transmission in white spaces. Thus, a need arises for a strategy that goes beyond simple channel utilization balancing, and uses frequency probing to profile channels according to their propagation properties. We devise VillageLink, a Gibbs sampling-based method that optimizes channel allocation in a distributed manner with a minimum number of channel switching events. Through extensive simulations we demonstrate that VillageLink results in a significant capacity improvement over alternative solutions.