In the seminal paper introducing their namesake algorithm for solving the mutual exclusion problem in a distributed system, Ricart and Agrawala assert (in the first paragraph of section 4 Message Traffic, on p. 13) that in a system comprising $N$ nodes the number of inter-node messages that their algorithm requires in order to allow an arbitrary node to enter its critical section is $2*(N-1)$, and that this number is the theoretically minimal one possible for any symmetric distributed mutual-exclusion algorithm when the nodes act independently and concurrently.
They explain why this number is the theoretically minimal possible as follows (section 4.1 Concurrent Processing, on p. 13):
For a symmetrical, fully distributed algorithm there must be at least one message into and one message out of each node. If no message enters/leaves some node, that node must not have been necessary to the algorithm; then the algorithm is not symmetrical or is not fully distributed. Furthermore, to allow the algorithm to operate concurrently at all nodes, the messages entering nodes must not wait for the message generated at the conclusion of processing at other nodes. This would indicate that two separate messages per node are required. The requesting node does not need to send and receive messages to itself, however, and so a total of $2*(N - 1)$ messages are needed. This number must be a minimum for any parallel, symmetric, distributed algorithm.
I don't understand the argument. Could you please explain it to me? Is there a way to formalize the argument? I believe I will understand the argument better if it is presented formally.
