Some emerging applications may require flexible playback features for time-based media, such as video, that cannot be directly supported by current compression standards, because for these decoding of frames can only be done in a predetermined order. An example would be a video application where both backward and forward frame-by-frame playback are to be supported. A standard codec could support this by decoding complete GOPs in the desired order, and then playing back one frame at a time. Thus, potentially significant added delay and memory are needed to support backward playback, which can be lowered if small GOP sizes are chosen, at the cost of reduced coding efficiency. Other example applications where flexible playback may be desirable include switching between different views in multiview video coding, and accessing individual spectral bands in hyperspectral imagery. In this work we address flexible playback by showing that it becomes feasible when a particular data unit (e.g., a video frame) can be decoded using information from either one of a number of other data units (e.g., in the video case the next frame or the previous frame). Note that this is different from structures such as bi-directionally predicted frames, which require both predictor frames to be available at the decoder. We cast this problem as one of source coding with uncertainty about decoder side-information and propose a solution based on distributed source coding. In addition, we propose macroblock-based mode switching algorithms in the context of distributed video coding to improve coding efficiency. Our results show that, using forward/backward playback as an example, our proposed solution can achieve good coding efficiency without incurring additional delay and memory overhead.