Systems and methods are presented for establishing network-wide time synchronization in a time-slotted barrage relay network. In the first phase, nodes obtain coarse, slot-level time synchronization by estimating the time-of-arrival (TOA) of a message that rapidly floods the network via the barrage relay mechanism. In the second phase, fine time synchronization is achieved via a messaging protocol that exchanges TOA information between neighboring nodes.