Previous work on multi-agent oriented constraintsatisfaction [8] shows that ERA is competitively suitable in solving the n-queen problem, and is capable of providing approximate solutions to different types of CSPs in about two or three time steps. Challenges remain in developing more efficient ERA based systems for solving CSPs beyond just approximation. In this paper, a modified ERA algorithm, involving a locality based heuristic and a random tie-breaking method, is proposed and tested. Experimental results have shown significant performance improvements, indicating some of the key characteristics and strengths of ERA as a multi-agent solution search process.