If you can bound partition durations, you can definitely make stronger guarantees.

If you can model your network delays, you can use some modeling like our work on PBS (Probabilistically Bounded Staleness) to predict staleness: http://pbs.cs.berkeley.edu/#demo