Replication is an effective way to improve the scalability, fault-tolerance, and availability as well as to reduce the query responding time in P2P system. With the P2P applications transferring from read-only static files sharing to read-write dynamical files interacting, maintaining consistency between frequently-updated files and their replicas is a fundamental reliability requirement for P2P system. This paper presents a trace label based consistency maintenance algorithm. It modifies the message datagram by attaching the address list of peers to which message has been sent. This can help to tell the duplicated message from the source peer by the aid of the attached address list in message datagram. Considering that the address list can become longer with the update time lapsing and the degree of P2P increasing, this paper presents a new Bloom Filter denoting the address list algorithm. The Bloom Filter can succinctly present the address list and simplify the query actions in the list by “OR” operations. The experimental results show that the new trace label based consistency maintenance algorithm can largely reduce the number of the duplicated messages. Moreover, the higher the degree of P2P, the more reduction of the number of duplicated messages and bandwidth utilization. The idea of consistency maintenance in this paper can also be applied to sensor network and other ad hoc networks.