This paper describes a distributed video transcoding system that can simultaneously transcode an MPEG-2 video file into various video coding formats with different rates. The transcoder divides the MPEG-2 file into small segments along the time axis and transcodes them in parallel. Efficient video segment handling methods are proposed that minimize the inter-processor communication overhead and eliminate temporal discontinuities from the re-encoded video. We investigate how segment transcoding should be distributed to obtain the shortest total transcoding time. Experimental results show that implementing distributed transcoding on 10 PCs can decrease the total transcoding time by a factor of about 7 for single transcoding and by a factor of 9.5 for simultaneous three kinds of transcoding rates.