What is the main difference between CRCW and EREW in PRAM model?

Question

In the PRAM model, multiple processors act synchronously to execute the same command on different sets of data.

There are two types of read/write mode for each algorithm;

1. Concurrent (Concurrent Read & Concurrent Write)
2. Exclusive (Exclusive Read & Exclusive Write)

What I find hard to understand is what exactly is the difference between these two modes, and which seems to be more proficient?

Answer 1

What if two processes attempt to read simultaneously from the same memory location ? (This operation is well defined.)

What if two processes attempt to write simultaneously into the same memory location ? (This operation is not so well defined: will the final value be one written by some of the processes ? If yes, which one ? Will it be a "mixture" ?)

You can design algorithms using one or the other models, i.e. allowing yourself concurrent reads/writes or not.

The most "powerful" machine is the CRCW model, it can give the fastest algorithms, followed by CREW.

Answer 2

Theory:

PRAM machines may harness one of the below listed principal approach to concurrent-events' handling policies not observed in any pure-[SERIAL] system.

Given the nature of the machine physical body, some of the below listed policies may ( but need not ) match the processing goals and software-based tools are then resorts to allow for other policies ( not listed below, thus not supported directly by the PRAM hardware-based resources ), sure, at a cost of additional time ( add-on overheads ) needed to mediate such policy enforcement steps and measures.

As observed in 3.2.x below, some of the hardware-based policies may become directly beneficial for specialised, not universal, image processing or similar cases, while a general purpose computing graph does not get correct results, if not protected by some means of exclusivity locking or atomic-operations, as none of the below listed CRCW-policies ensures systematically valid result in otherwise uncoordinated a "just"-[CONCURRENT] scheduled code-execution concurrency-originated colliding write-accesses.

---

• EREW ( Exclusive Read, Exclusive Write ):

1.1) Concurrent memory access by multiple processors is not allowed
1.2) If two or more processors try to read from or write to the same memory cell concurrently, the behaviour is undefined

---

• CREW ( Concurrent Read, Exclusive Write ):

2.1) Reading the same memory cell concurrently is OK
2.2) Two concurrent writes to the same cell lead to unspecified behaviour

---

• CRCW ( Concurrent Read, Concurrent Write ):

3.1) Concurrent reads and writes are both OK
3.2) Behavior of concurrent writes has to be further specified:

3.2.1) Weak-CRCW: concurrent write only OK if all processors write 0
3.2.2) Common‐mode-CRCW: all processors need to write the same value
3.2.3) Arbitrary‐winner-CRCW: adversary picks one of the values ( a lottery indeed )
3.2.4) Priority-CRCW: value of processor with highest ID is written
3.2.5) Strong-CRCW: { largest | smallest }-value is written