Abstract: Non-rigorous statistical mechanics ideas have inspired a message passing algorithm called Belief propagation guided decimation for finding satisfying assignments of random k-SAT instances. This algorithm can be viewed as an attempt at implementing a certain thought experiment that we call the decimation process. In this paper we identify a variety of phase transitions in the decimation process and link these phase transitions to the performance of the algorithm.