  Parallel systems have received increasing attention with numerous recent
applications such as fork-join systems, load-balancing, and l-out-of-k
redundancy. Common to these systems is a join or resequencing stage, where
tasks that have finished service may have to wait for the completion of other
tasks so that they leave the system in a predefined order. These
synchronization constraints make the analysis of parallel systems challenging
and few explicit results are known. In this work, we model parallel systems
using a max-plus approach that enables us to derive statistical bounds of
waiting and sojourn times. Taking advantage of max-plus system theory, we also
show end-to-end delay bounds for multi-stage fork-join networks. We contribute
solutions for basic G|G|1 fork-join systems, parallel systems with
load-balancing, as well as general (k,l) fork-join systems with redundancy. Our
results provide insights into the respective advantages of l-out-of-k
redundancy vs. load-balancing.
