A predestination paradox is a form of causal loop where events in the future cause events in the past which then lead to events in the future. In such instances it is impossible to ever say for sure which events occur first. In the case of a predestination paradox, some event in the future causes events to occur in the past without altering the timeline.
Theory
Many theories of time travel hold that time itself wants to happen, or to put it another way, time travel is part of the natural evolution of science and thus at some point there will be time travelers who go to the past and alter the timeline and thus it is fate that such events occur and they are thus meant to occur. Since it is already fated to occur then there is no change (or negligible) change in the events occurring after the changes to the timeline.
This theory has yet to be confirmed due to the nature of its thesis, fate cannot be proven or disproven.
Corrective Action vs. Predestination
It has often been discussed if the theory of this kind of paradox means that, if true, this paradox is a corrective action taken by the natural course of the timeline to correct itself. Corrective actions taken by Solas Tempus or other organizations / individuals would thus be examples of predestination paradoxes every time alterations to the timeline occurred and were corrected.
The prevailing theory in temporal mechanics is that a true paradox could only occur when alterations to the timeline did not produce a temporal wave which would then spark an organization to take corrective actions. This is a hot topic for philosophical debate and many consider it a question to the nature of the universe, which also cannot be answered except as a philosophical point.