At the end of the section “Parallel and distributed computing”, I wrote:
(It should be clear that I didn’t really try to read those texts, and just browsed through them.)
Well, I worked through the survey “Parallel Algorithms” by G. Blelloch and B. Maggs in the meantime, and finished the first quarter of “Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques” by U. Vishkin. The terms EREW, CREW, CRCW (E=exclusive, C=concurent, R=read, W=write) are explained, but their detailed relation to NC1, L, NL, SAC1, and AC1 is not discussed. I found such a discussion (including t…
(It should be clear that I didn’t really try to read those texts, and just browsed through them.)
Well, I worked through the survey “Parallel Algorithms” by G. Blelloch and B. Maggs in the meantime, and finished the first quarter of “Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques” by U. Vishkin. The terms EREW, CREW, CRCW (E=exclusive, C=concurent, R=read, W=write) are explained, but their detailed relation to NC1, L, NL, SAC1, and AC1 is not discussed. I found such a discussion (including t…