  One of the key ways in which quantum mechanics differs from relativity is
that it requires a fixed background reference frame for spacetime. In fact,
this appears to be one of the main conceptual obstacles to uniting the two
theories. Additionally, a combination of the two theories is expected to yield
non-classical, or "indefinite", causal structures. In this paper, we present a
background-independent formulation of the process matrix formalism - a form of
quantum mechanics that allows for indefinite causal structure - while retaining
operationally well-defined measurement statistics. We do this by postulating an
arbitrary probability distribution of measurement outcomes across discrete
"chunks" of spacetime, which we think of as physical laboratories, and then
requiring that this distribution be invariant under any permutation of
laboratories. We find (a) that one still obtains nontrivial, indefinite causal
structures with background independence, (b) that we lose the idea of local
operations in distinct laboratories, but can recover it by encoding a reference
frame into the physical states of our system, and (c) that permutation
invariance imposes surprising symmetry constraints that, although formally
similar to a superselection rule, cannot be interpreted as such.
