Summary: Achieving fair bandwidth allocation in a P2P streaming scenario is even more difficult, as it comes with an additional constraint: each stream update must be received before its playback deadline P2P live streaming systems require global resource over-provisioning to deliver adequate streaming performance. When there is not enough bandwidth to accommodate all users for a particular stream, such as due to free-riders or low-contributing peers, all users, including high-contributing peers, observe poor performance. We present FairStream, a new P2P streaming system that delivers a good quality stream to peers that upload data at a rate above the stream rate, even in the presence of free-riders or malicious users. FairStream achieves this with three mechanisms. First, it provides a new peer reply policy framework that enables file sharing incentive mechanisms to be adapted for streaming. Second, it uses this framework to incorporate a deficit-based peer reply policy that enables each peer to reply first to the neighbor to whom it owes the most data as measured by a deficit counter. Third, it introduces a collusion-resistant mechanism to ensure effective data distribution of a stream despite a large fraction of free-riders who do not forward received data. We prove that FairStream is resilient to free-riders and rewards peers with streaming performance correlated with their contributions. We have also implemented FairStream as a BitTorrent client and evaluated its performance against other popular streaming systems. Our results on PlanetLab show that FairStream, similar to other systems, provides good quality streaming performance when resources are over-provisioned, but it also provides orders of magnitude better streaming performance for peers uploading above the stream rate when resources are constrained, in the presence of free-riders and low-contributing peers.