This paper presents a heuristically-aided algorithm to achieve mutual exclusion in distributed systems which has better performance characteristics than the algorithm of Suzuki and Kasami, which in turn is an improvement over the well-known Ricart and Agrawala algorithm for mutual exclusion. The proposed algorithm makes use of state information, which is defined as the set of states of mutual exclusion processes in the system. Each site maintains information about the state of other sites and uses it to deduce a subset of sites likely to have the token. Consequently, the number of messages exchanged for a critical section invocation is a random variable between 0 and n ("n" is the number of sites in the system). We show that the algorithm achieves mutual exclusion and is free from deadlock and starvation. We discuss the effects of a site crash and a communication medium failure on the proposed algorithm by a simulation technique (and by an analytic technique for low and heavy traffics of requests for critical section execution). The proposed algorithm also serves as an illustration of the effectiveness of heuristic techniques applied to problems where a system must satisfy strong constraints such as database consistency or mutual exclusion.