After a brief introduction to issues that plague the realization of a theory of quantum gravity, I suggest that the main one concerns defining superpositions of causal structures. This leads me to a distinction between time and space, to a further degree than that present in the canonical approach to general relativity. With this distinction, one can make sense of superpositions as interference between alternative paths in the relational configuration space of the entire Universe. But the full use of relationalism (...) brings us to a timeless picture of Nature, as it does in the canonical approach. After a discussion of Parmenides and the Eleatics' rejection of time, I show that there is middle ground between their view of absolute timelessness and a view of physics taking place in timeless configuration space. In this middle ground, even though change does not fundamentally exist, the illusion of change can be recovered in a way not permitted by Parmenides. It is recovered through a particular density distribution over configuration space which gives rise to 'records'. Incidentally, this distribution seems to have the potential to dissolve further aspects of the measurement problem that can still be argued to haunt the application of decoherence to Many-Worlds quantum mechanics. I end with a discussion indicating that the conflict between the conclusions of this paper and our view of the continuity of the self may still intuitively bother us. Nonetheless, those conclusions should be no more challenging to our intuition than Derek Parfit's thought experiments on the subject. (shrink)