A long-standing tradition, largely present in both the physical and the philosophical literature, regards the advent of (special) relativity -- with its block-universe picture -- as the failure of any indeterministic program in physics. On the contrary, in this paper, we note that upholding reasonable principles of finiteness of information hints at a picture of the physical world that should be both relativistic and indeterministic. We thus rebut the block-universe picture by assuming that fundamental indeterminacy itself should as well be regarded as a relational property when considered in a relativistic scenario. We discuss the consequence that this view may have when correlated randomness is introduced, both in the classical case and in the quantum one.