A new adaptive gossip-based membership management algorithm is proposed. Its adaptive nature enables it to con- fine the control overhead to local ranges, and adapt to the ever-changing network traffic conditions and group membership. The random nature of the algorithm ensures that it can cope with random failures and offer proactive measures to maintain service at a certain level. Mathematical analysis and simulation results indicate that more than 90% of the nodes can work properly even under very high network dynamics (with a short half-life time of 50 seconds), and all these are achieved by using a relatively low overhead.