This paper presents a novel cooperative recording scheme in networked PVRs based on P2P networks to increase storage efficiency compared with when PVRs operate independently of each other, while maintaining program availability to a similar degree. We employ an erasure coding technique to guarantee data availability of recorded programs in P2P networks. We determine the data redundancy degree of recorded programs so that the system can support all the concurrent streaming requests for them and maintain as much availability as needed. We also present how to assign recording tasks to PVRs and playback the recorded programs without performance degradation. We show that our proposed scheme improves the storage efficiency significantly, compared with when PVRs do not cooperate with each other, while keeping the playbackability of each request similarly.