Can Multipath Mitigate Power Law Delays? - Effects of Parallelism on Tail Performance

摘要

Parallelism is a common approach to improve reliability and efficiency in practice. For instance, in peer to peer systems, a file is downloaded in parallel from multiple peers. In one type of parallelism, a file is fetched in its entirety, and hence the completion time is the minimum of the completion times from the multiple locations. In another type of parallelism, a file is split into multiple pieces, fetched independently, and hence the completion time is the maximum of the completion times of all the pieces. In both cases, we expect better efficiency from using parallelism since the delay is either the minimum one or because a smaller job needs to be completed.