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 also be regarded as a relative 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.