Distributed Mutual Exclusion Problem in Cellular Automata
Souvik Roy and Sukanta Das
This work introduces the mutual exclusion problem in the domain of cellular automata (CAs). We show that it is impossible to solve this problem by a 1-D CA under periodic boundary condition for all possible initial configurations. We, then, classify the valid initial configurations of 1-D CAs into six classes, and show that for some classes of initial configurations, it is possible to get a CA-based solution for the problem.
Keywords: Cellular automata (CAs), mutual exclusion problem, critical section (CS).