The paper presents simple parallel algorithms for the maximal independent set (MIS) problem, focusing on a Monte Carlo algorithm with a local property. The main contributions include techniques for converting Monte Carlo algorithms into deterministic ones, which are used to develop a simple deterministic algorithm with the same parallel running time. The first algorithm is analyzed in detail, showing that it can be implemented efficiently on an EREW P-RAM with a small number of random bits. The paper also discusses the application of MIS algorithms in other problems, such as maximal coloring and maximal matching, and explores their potential in distributed computing and artificial intelligence. Additionally, the paper addresses the Binary Coherent System problem, a special case of the MIS problem, and its relevance to connectionist models of the brain. Finally, the paper outlines open problems and future research directions, including the need for lower bounds on the parallel complexity of the MIS problem.The paper presents simple parallel algorithms for the maximal independent set (MIS) problem, focusing on a Monte Carlo algorithm with a local property. The main contributions include techniques for converting Monte Carlo algorithms into deterministic ones, which are used to develop a simple deterministic algorithm with the same parallel running time. The first algorithm is analyzed in detail, showing that it can be implemented efficiently on an EREW P-RAM with a small number of random bits. The paper also discusses the application of MIS algorithms in other problems, such as maximal coloring and maximal matching, and explores their potential in distributed computing and artificial intelligence. Additionally, the paper addresses the Binary Coherent System problem, a special case of the MIS problem, and its relevance to connectionist models of the brain. Finally, the paper outlines open problems and future research directions, including the need for lower bounds on the parallel complexity of the MIS problem.