Heavy-Tailed Behaviour in Randomised Systematic Search Algorithms for SAT?

Prompted by recent results reported by Carla Gomes, Bart Selman, and Henry Kautz, and in the context of my ongoing project with Thomas Stuetzle on characterising the behaviour of state-of-the-art algorithms for SAT, I measured some run-time distributions for Satz-Rand, the randomised version of the Satz algorithm, when applied to problem instances from various domains. I could not find truly heavy-tailed behaviour (in the sense of the definition used by Carla Gomes et.al.). Instead, I found evidence for multimodal distributions which might be characterisable using mixtures of the generalised exponential distributions introduced in (Hoos, 1999). However, the observed RTDs typically have long tails and random restart, using suitable cutoff times, increases the efficiency of the algorithm, as claimed by Gomes et.al. Furthermore, taking another look at the issue of heavy tails at the left-hand side of run-time distributions, I raise some questions regarding the arguments found in (Gomes et.al., 2000).