Abstract: To implement fault detection under large-scale, strong dynamic, high reliability required network environments, the traditional fault message dissemination would encounter network congestion, latency instability etc.. A fault detection protocol based on self-organized neighborhood construction is proposed, and agent nodes are chosen to implement detection between neighborhoods. In every single zone, a random dissemination fault detection algorithm called Self-Organized Neighborhood Fault Detection Protocol (SONFDP) is designed. This protocol can avoid network congestion caused by flood, reduce the network overhead and extend the scalability of fault detection. Meanwhile, a mechanism of redundant message avoidance is designed to further reduce the number of messages generated by detection. SONFDP is proven to be correct and effective by relevant mathematical analysis and experiments.