Abstract: Distributed media systems, transparently embedded in the surroundings to provide information-based services to human users, have to rely on real-time media processing technologies to: (a) continuously sense users' needs, status, and the context; (b) filter and fuse a multitude of real-time media data, and adapt the environment to the user. One common aspect of these systems is that they need to process various media data collected through environmental sensors and react by actuating appropriate responses in real-time. Architecture for Interactive Arts (ARIA) is composed of three main layers to incorporate real-time captured media into live performances, on-demand. The design and visualization layer enables choreographers to specify sensory/reactive tasks, which the processing layer has to continuously track and execute. These tasks are represented in terms of media processing workflows. This dissertation mainly focuses on modeling and description of media processing workflows and adaptive and quality-aware workflow processing in the ARIA project. First, this dissertation introduces a graph-based model for quality adaptive media processing workflows which describe how the data sensed through media sensors will be processed and what audio-visual responses will be actuated. The media capture and processing components, which are characterized by individual parameters (i.e. processing precision and cost), are programmable and adaptable. A particular challenge with such parametric systems is to choose the appropriate parameters at runtime. This dissertation exploits transformation histories carried by the objects for processing by the operators to determine the optimal way to process the object in presence of the quality/cost trade-off. This dissertation presents graph-theoretical solutions to obtain least-delay or high-precision output streams under different Quality of Service (QoS) requirements. Second, when faced with resource limitations, ARIA utilizes quality- and cost-aware adaptation strategies for load shedding. When operators are overloaded, quality-assessment models for media objects and filter and fusion operators, are established, with the goal of enabling effective quality- and cost-aware load shedding in media-rich sensory systems. This dissertation builds on the quality-assessment models to develop prediction schemes that will enable confidence-based early object elimination and combination-shedding schemes which rely on partial orderings of input, object combinations to enable effective top-k combination selection.