(n, k) fork-join queues are prevalent in popular distributed systems, erasure coding based cloud storages, and modern network protocols like multipath routing, estimating the sojourn time of such queues is thus critical for the performance measurement and resource plan of computer clusters. However, the estimating keeps to be a well-known open challenge for years, and only rough bounds for a limited range of load factors have been given. This paper developed a closed-form linear transformation technique for jointly-identical random variables: An order statistic can be represented by a linear combination of maxima. This brand-new technique is then used to transform the sojourn time of non-purging (n, k) fork-join queues into a linear combination of the sojourn times of basic (k, k), (k + 1, k + 1), ..., (n, n) fork-join queues. Consequently, existing approximations for basic fork-join queues can be bridged to the approximations for non-purging (n, k) fork-join queues. The uncovered approximations are then used to improve the upper bounds for purging (n, k) fork-join queues. Simulation experiments show that this linear transformation approach is practiced well for moderate n and relatively large k.
A typical use case of non-purging @math fork-join queues is the writing process in Cassandra @cite_0 . @cite_9 gave non-asymptotic statistical bounds on the sojourn time of non-purging @math fork-join queues. As a contrast, we give proper approximations instead of bounds.
@cite_0 @cite_9
2066799377 2963083228
Inherent replica inconsistency refers to the difference among the replicas of the same logical data item in the write propagation process of a normally running distributed storage system. In this paper, we formalize the write propagation process model of Cassandra, a widely used NoSQL storage system. In the write propagation process we explore two queueing systems, sending task queues and mutation queues, which locate at each replica node and are determinants of the replica inconsistency. The departure time difference from the mutation queue is used as the measure of inconsistency between two replicas. Furthermore, Request Per Second (RPS) and Mutation Threads Number (MTN), which affect the inherent inconsistency, are discussed and the MTN adaptation algorithm is proposed. Finally, A Cassandra inconsistency measurement framework is implemented using the source instrumentation approach. The empirical results conform well with our proposed inconsistency measurement model. Parallel systems have received increasing attention with numerous recent applications such as fork-join systems, load-balancing, and l-out-of-fc 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.