We develop and analyze efficient distributed algorithms for a constrained convex optimization problem over a multi-agent network where each agent has its own objective function and constraint set. We propose gradient descent algorithms with random projections under various communication protocols. With standard assumptions, we prove that the iterates of all agents converge to the same point in the optimal set with probability 1. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and establish its convergence. We also provide experimental results to demonstrate the efficiency of the algorithms.