This paper considers optimal distributed beamforming designs in a multi-relay network with multiple sources and multiple destinations. It is assumed that all source-destination pairs operate in orthogonal channels to avoid inter-user interference at the destinations. The distributed beamforming designs are carried out to minimize the sum relay power with guaranteed quality of service (QoS) in terms of signal-to-noise-ratio (SNR) at the destinations. Considered are optimization problems with and without per-relay power constraints. Although the two optimization problems can be readily transformed into convex second-order conic programs (SOCPs), the paper proposes simple and fast iterative algorithms to efficiently solve them.