How can massless gluons interact with each other? Massless particles, such as photons and gluons, move with the speed of light and consequently experience no time. According to Special Relativity, time stops at the speed of light. As a result, massless particles exist in the same moment of their proper time from the emission to absorption. Therefore massless particles cannot decay or experience any other change. A practical example of this logic is that neutrinos have mass, because massless neutrinos cannot oscillate.
It seems that two massless particles that don't experience time should not be able to interact with each other (at least without the interaction mediated by virtual massive particles). This holds true for photons not interacting with each other (in the first order) resulting in the linearity of the electromagnetic field.
QCD is a non-linear theory with gluons interacting with each other via 3 and 4 vertices. Specifically the 3-gluon vertex (please correct me if I am wrong) under specific conditions can be viewed as a gluon decay into two gluons. However, massless particles cannot decay according to Special Relativity. What is the explanation of why massless gluons can interact with each other and apparently even decay while not experiencing time?
 A: That's...not how special relativity works.
Your question seems predicated on the idea that massless particles "experience no time", because special relativity says that "time stops at the speed of light". Neither of these is true, see this answer by Ben Crowell. The point is that the notion of "experiencing time" is ill-defined for particles moving at the speed of light, since there simply is no notion of frame for a hypothetical observer moving at the speed of light (because the formula for Lorentz transformations diverges as $v\to c$, a manifestation of the non-compactness of the Lorentz group). Ill-defined does not mean that "time stops", it means it is not meaningful to try to speak about the "time experienced by an object moving at the speed of light" at all.
As a side remark, a single massless particle is indeed forbidden by relativity to decay into two daughter particles! But not because of any mystical rule imposed by it "not experiencing time", but simply because such a decay cannot fulfill the kinematic constraints of energy and momentum conservation.
A: In our laboratory experiments gluons are always off mass shell so the problem does not arise as they take virtual masses under the integrals.
Your question would be relevant in the quark gluon plasma at cosmological times, where anyway symmetry is unbroken and all elementary particles in the table have zero mass. Calculations are not done in the rest system of zero mass particles,  but in some appropriate observer frame, and interactions take place following the rules of quantum field theory. 
After all there are photon photon interactions in our laboratory experiments, higher order, but still there, and gamma gamma colliders are being proposed. They will be studied in the laboratory frame, not in the system of one of the gammas!!
