The experimental search of non-conventional effects predicted by bottom-up approaches and theoretical models of quantum gravity is a quite recent field of research. Generically, it requires to consider probes of very high energy and amplification mechanisms, conditions which are fulfilled by the propagation of the cosmic messengers. Advances in multi-messenger astronomy during the last decade has driven progress in the field, but a number of theoretical and experimental challenges still lie ahead. We will review them, making emphasis in two complementary lines of research: the study of time delays and the modification of interactions which appear in quantum-gravity motivated extensions of special relativity.