Модель PRAM

Алгоритмы рассматриваемые здесь будут основаны на параллельном варианте такой машины, называемом PRAM. Процессоры нашей PRAM-машины тесно связаны между собой и пользуются общим блоком памяти. В каждом процессоре есть несколько регистров, в которых может храниться небольшой объем данных, однако основная часть данных содержится в общей памяти.
У нас есть четыре комбинации возможностей чтения и записи: конкурентное чтение / конкурентная запись (CRCW), конкурентное чтение / исключительная запись (CREW), исключительное чтение / конкурентная запись (ERCW), исключительное чтение / исключительная запись (EREW).