A distributed video-on-demand (VoD) system is one where collection of video data is located at dispersed sites across a computer network. In a single site environment, a local video server retrieves video data from its local storage device. However, in the setting of a distributed VoD system, when a customer requests a movie from the local server, the server may need to interact with other servers located across the network. In this paper, we present three types of presentation plans that a local server must construct in order to satisfy the customer request. Informally speaking, a presentation plan is a temporally synchronized detailed sequence of steps that the local server must perform for presenting the requested movie to the customer. This involves obtaining commitments from other video servers, obtaining commitments from the network service provider, as well as making commitments of local resources, within the limitations of available bandwidth, available buffer, and customer data consumption rates. Furthermore, for evaluating the goodness of a presentation plan, we introduce two measures of optimality for presentation plans: minimizing wait time for a customer, and minimizing access bandwidth is used. We develop algorithms to compute optimal presentation plans for all three types, and carry out extensive experiments to compare their performance. We have also mathematically proved certain results for the presentation plans that had previously been verified experimentally in the literature.