This paper discusses the Quality of Service (QoS) negotiations for orchestrated, distributed multimedia presentation and presents solution based on the temporal relationships between the objects composing the presentation, for determining and negotiating the QoS requirements. Presented are algorithms for deriving the preferred and acceptable QoS values which can be used for negotiation. Also given, are algorithms for handling user interactions and dynamic behaviour of the network service provider. Finally, presented is a Finite State Machine Model to describe the QoS negotiation process for an orchestrated, distributed multimedia presentation with user participation.