Big Oh in the parallel world

Big-Oh notation is a simple and powerful way to express how running time of a particular algorithm depends on the size of the input. But, what about the complexity of parallel programs? There are several ways to incorporate this variable into the Big-Oh notation, and I am going to describe them one-by-one.