  It has been recently observed that small violations of Lorentz invariance, of
a type which may arise in quantum gravity, could explain both the observations
of cosmic rays above the GZK cutoff and the observations of 20-TeV gamma rays
from Markarian 501. We show here that different pictures of the short-distance
structure of space-time would lead to different manifestations of
Lorentz-invariance violation. Specifically, the deformation of Lorentz
invariance needed to resolve these observational paradoxes can only arise
within commutative short-distance pictures of space-time. In noncommutative
space-times there is no anomalous effect, at least at leading order. Also
exploiting the fact that arrival-time delays between high energy photons with
different energies would arise in both the commutative and the noncommutative
Lorentz-violation pictures, we describe an experimental programme, based on
time-of-arrival analysis of high energy photons and searches of violations of
GZK and TeV-photon limits, which could discriminate between alternative
scenarios of Lorentz-invariance breakdown and could provide and unexpected
window on the (quantum) nature of space-time at very short distances.
