Various models:
EREW (exclusive read, exclusive write)
CREW (concurrent read, exclusive write)
CRCW (concurrent read, concurrent write)
Here: problems with concurrent writes
▶
common: all the same
▶
priority: processors are sorted by priority; if more than one want to
write, highest priority wins
▶
arbitrary: well, arbitrary one wins
▶
majority: many sub-models (>half, relative majority, . . . )
Obviously: EREW “≤” CREW “≤” CRCW
T Design of Algorithms. . . Part 3 2021/22 4 / 70
