—In distributed file systems, Random-Linear-Coding (RLC) reduces scheduler complexity and download time by eliminating the coupon collector problem [1]. Similar benefits for video streaming in Distributed Video Caching and Sharing (DVCS) systems require segmentation of videos into codeblocks, over which RLC can be applied, to ensure videos' quality. This research proposes RLC-based DVCS (RLC-DVCS), and shows that RLC reduces complexity of the distributed video caching decision from which video chunks to how many RLC chunks to cache at each mobile device, and better facilitates distributability of content among devices (more mobile devices dedicating fewer resources each). All while increasing the number of video requests served on-time from DVCS, despite the challenges of video streaming. RLC-DVCS utilizes optimization and approximation methods for video segmentation, cache selection and allocation, to ensure videos' quality and cache more videos of highest request probability by reducing distributed size of each video. Using lagrangian relaxation allows for distributed RLC-DVCS where each mobile device decides how many RLC chunks to cache with limited coordination from other devices or a centralized scheduler. Monte Carlo evaluation of the proposed methods shows that RLC-DVCS achieves higher recovery probability than symmetric allocation of RLC chunks across mobile devices or un-coded DVCS.