Recently, a new server-less architecture is proposed for building low-cost yet scalable video streaming systems. In this architecture, video blocks are distributed among user hosts and these hosts cooperate to stream video blocks to one another. To improve reliability, data and capacity redundancy are introduced to sustain node failures. However, the data placement as well as the redundant data in the system will need to be updated whenever new nodes join the system. Results show that the redundancy update overhead is very significant and even exceeds that in data reorganization. In this study, we present a new Transpositional Redundant Data Update algorithm that takes advantage of the structure of Reed-Solomon Erasure Correction codes and employs a special encoding scheme to significantly reduce the redundancy update overhead, especially when updates are performed in batch.