The communication requirements of mutual exclusion
Robert Cypher · 1995
This paper examines the amount of communication that is required for performing mutual exclusion.It is assumed that n processors communicate via accesses to a shared memory that is physically distributed among the processors.We consider the possibility of creating a scalable mutual exclusion protocol that requires only a constant amount of communication per access to a critical section.We present two main results, First, we show that there does not exist a scalable mutual exclusion protocol that uses only read and write operations.This result solves an open problem posed by Yang and Anderson, Second, we prove