A multi-relay network is studied in which communication from source to relays takes place over a Gaussian broadcast channel, while the relays are connected to the receiver via orthogonal finite-capacity links. Unbeknownst to the source and relays, link failures may take place between any subset of relays and the destination in a non-ergodic fashion. Upper and lower bounds are derived on average achievable rates with respect to the prior distribution of the link failures. It is first assumed that relays are oblivious to the codebook shared by source and destination, and then the results are extended to the nonoblivious case. The lower bounds are obtained via strategies that combine the broadcast coding approach, previously investigated for quasi-static fading channels, and different robust distributed compression techniques.