One of the challenges of today?s overlay networks, especially P2P, is still scalability. A key issue in almost all of the current overlay architectures is the link count per single node. If the link count is too high, the management overhead in terms of keep-alive messages increases. If the amount of links per node is too low, the resilience of the system against network splits decreases and the system can hardly route in an optimal way. Moreover, if keep-alive messages are not sent frequently enough, outdated information could be propagated, which again could cause net splits. This paper presents a new cooperative keep-alive algorithm that strongly reduces the costs for sending keepalive messages and, at the same time, preserves the effectiveness and reliability of standard keep-alive mechanisms in today?s overlay networks. The algorithm allows to increase the number of links per node, and, thus, to improve the connectivity and routing efficiency in the network, while keeping the keep-alive overhead low. When used without increasing the link count, the algorithm reduces drastically the keep-alive traffic. The properties of the algorithm are evaluated analytically and simulatively and compared to existing keep-alive techniques.