The authors present an algorithm for bandlimited signal interpolation, assuming the samples to be known at some randomly distributed instants. The algorithm is a modification of the Papoulis-Gerchberg algorithm. The key idea is to use at the missing points nonzero values that are obtained using an interpolation scheme based on a relaxation method for constraint propagation. The algorithm is illustrated with several examples.