  Our understanding of the Universe breaks down for very small spacetime
intervals, corresponding to an extremely high level of granularity (and
energy), commonly referred to as the ``Planck scale''. At this fundamental
level, there are attempts of describing physics in terms of interacting
automata that perform classical, deterministic computation. On one hand,
various mathematical arguments have already illustrated how quantum laws (which
describe elementary particles and interactions) could in principle arise as
low-granularity approximations of automata-based systems. On the other hand,
understanding how such systems might give rise to relativistic laws (which
describe spacetime and gravity) remains a major problem. I explain here a few
ideas that seem crucial for overcoming this problem, along with related
algorithmic challenges that need to be addressed. Giving emphasis to meaningful
computational counterparts of locality and general covariance, I outline basic
ingredients of a distributed communication-rewiring protocol that would allow
us to construct multi-automaton models that are viable from a relativistic
perspective. I also explain how viable models can be evaluated using a variety
of criteria, and discuss related aspects pertaining to the falsifiability and
plausibility of the automata paradigm.
