Techniques for determining network reliability using message success rates include receiving, by a first node and for a plurality of respective potential parent nodes, respective accumulated uplink message success rates, wherein a respective accumulated uplink message success rate for a respective potential parent node indicates a probability of successfully transmitting messages from that respective potential parent node to a target destination; determining, by the first node, respective local uplink message success rates for the plurality of respective potential parent nodes, wherein a respective local uplink message success rate indicates a probability of successfully transmitting messages from the first node to that respective potential parent node; and selecting, by the first node based on the respective accumulated uplink message success rates and the respective local uplink message success rates, a first respective potential parent node from the plurality of respective potential parent nodes as a parent node.