The numerical instability of GS is due to loss of orthogonality, not so much errors in normalization.

Householder and Givens approaches are about equal AFAIK, but the wikipedia article claims Givens is easier to parallelize. I am not sure that applies for Map-Reduce. Givens is definitely easier to apply in a sparse case since you don't have to deal with an entire (mostly zero) row or column at a time.

Golub and van Loan, p 219 (2nd edition) has a discussion that shows that the error for **modified** Gram-Schmidt is about k u where k is the condition number of the matrix and u is a single ULP while Householder and Givens approaches have error about the same as u. This implies that hilbert matrices might be good test cases.

I've made an implementation according to http://en.wikipedia.org/wiki/QR_decomposition but I still have a problem: I get an error caused by storing doubles in memory and resulting in calculations error(actually taking square root when calculating vector norm). So we normally get non-integer determinant for matrix of integers(still it's close to desired value)... This can actually result in significant error for big matrix