  One of the most puzzling current experimental physics paradoxes is the
arrival on Earth of Ultra High Energy Cosmic Rays with energies above the GZK
threshold. The recent observation of 20TeV photons from Mk 501 is another
somewhat similar paradox. Several models have been proposed for the UHECR
paradox. No solution has yet been proposed for the TeV-$\gamma$ paradox.
Remarkably, the drastic assumption of a violation of ordinary Lorentz
invariance would resolve both paradoxes. We present a formalism for the
description of the type of Lorentz-invariance deformation (LID) that could be
induced by non-trivial short-distance structure of space-time, and we show that
this formalism is well suited for comparison of experimental data with LID
predictions. We use the UHECR and TeV-$\gamma$ data, as well as bounds on
time-of-flight differences between photons of different energies, to constrain
the LID parameter space. A model with only two parameters, an energy scale and
a dimensionless parameter characterizing the functional dependence on the
energy scale, is shown to be sufficient to solve both the UHECR and the
TeV-$\gamma$ threshold anomalies while satisfying the time-of-flight bounds.
The allowed region of the two-parameter space is relatively small, but,
remarkably, it fits perfectly the expectations of the quantum-gravity-motivated
space-time models known to support such deformations of Lorentz invariance:
integer value of the dimensionless parameter and characteristic energy scale
constrained to a narrow interval in the neighborhood of the Planck scale.
