Methods and systems are provided for optimally trading off replication
overhead and consistency levels in distributed data replication where
nodes are organized in a hierarchy. The root node has the original data
that need to be replicated at all other nodes, and the replicated copies
have a freshness threshold that must be satisfied. The data are
propagated through periodic updates in the hierarchy. Each node
periodically sends data to its child nodes. Given the freshness
threshold, an algorithm and its distributed protocol can determine the
optimal update period for each link of the hierarchy such that the
freshness threshold is satisfied for every node and the overall
replication overhead is minimized. The systems and methods can be used in
any scenario where replicated data have consistency requirements, such as
in a replicate overlay assisted resource discovery system.