# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
We assume that each process receives as input the whole array \(A\), for instance, every process reads the input from a file or a designated process reads it and broadcasts it to the other processes. Therefore, there is no need to use message-passing to perform the initial domain decomposition. Next, the algorithm locally estimates the quantile \(q\) for its sub-array. The modification required to the sequential Frugal-1U is trivial, and consists of coding a linear scan of the sub-array using a _for_ loop starting at \(left\) and ending at \(right\). Once the local estimates \(\tilde{m}_{id}\), \(id=0,\cdots p-1\) have been found, the processors engage in a parallel reduction operation by invoking the ParallelReduction algorithm passing as input the pair \((\tilde{m}_{id},size_{id})\). Its purpose is to determine the global estimate of the quantile \(q\) for the whole array \(A\), and this is done by using the parallel reduction operator of Algorithm 5. The parallel reduction can be either a standard user's defined parallel reduction in which only one of the processors obtains the result at the end of the computation or it may be an all-reduction, which differs because in this case all of the processors obtain the result at the end of the computation. In practice, an all-reduction is equivalent to a reduction followed by a broadcast operation. Here, we choose a standard reduction in which we assume that the processor with rank equal to zero will obtain the final result but, in this case, it is trivial to use an all-reduction if required. As shown in Algorithm 5, the parallel reduction takes as input two pairs \((\hat{m}_{i},n_{i})\) and \((\hat{m}_{j},n_{j})\) produced by processors \(i\) and \(j\) and returns the pair \((\hat{m},w)\), where \(w=n_{i}+n_{j}\) and \(\hat{m}=(\hat{m}_{i}n_{i}+\hat{m}_{j}n_{j})/w\). ```
pairs \((\hat{m}_{i},n_{i})\) and \((\hat{m}_{j},n_{j})\) produced by processors \(i\) and \(j\) estimated quantile value \(\hat{m}\), weight \(w\) \(w=n_{i}+n_{j}\); \(\hat{m}=(\hat{m}_{i}n_{i}+\hat{m}_{j}n_{j})/w\) return\((\hat{m},w)\)
```

**Algorithm 5** Parallel reduction operator

The corresponding parallel versions for Frugal-2U and EasyQuantile are obtained by substituting these algorithms in place of the invocation of Frugal-1U in Algorithm 4, since Algorithm 5 is the same for all of the algorithms. Similar considerations can be used to derive the distributed versions. It is worth noting here that, from a practical perspective, the only differences between a parallel algorithm and a distributed one are the following: (i) the distributed nodes' hardware may be heterogeneous, whilst a parallel machine is typically equipped with identical processors; (ii) the network connecting the distributed nodes is typically characterized by relatively high latency and low bandwidth, whilst, on the contrary, the interconnection network of a parallel machine provides ultra low latency and high bidirectional bandwidth; (iii) some of the distributed nodes may fail in unpredictable ways whilst we expect the nodes of a parallel machine to be always up and running (except for scheduled maintenance). As a consequence, only the performance may be affected whilst the accuracy is identical. Here, we are assuming that the distributed nodes stay up and running during the distributed computation. ## 6 Analysis of the Algorithm

Here, we derive the parallel complexity of the algorithm (the analysis applies to Frugal-2U and EasyQuantile as well). At the beginning, the workload is balanced using a block distribution; this is done with two simple assignments; therefore, the complexity of the initial domain decomposition is O(1). Determining a local estimate \(\hat{m}_{id}\) invoking the Frugal-1U algorithm requires in the worst case \(O(n/p)\) time, since the running time of the sequential algorithm is linear and the sub-array to be processed consists of either \(\lfloor n/p\rfloor\) or \(\lceil n/p\rceil\) items. Determining the weight \(size_{id}\) requires worst case \(O(1)\) time.