# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
Figure 8:4 Parallel EasyQuantile on workstation: strong and weak scalability. Figure 8:5 Parallel EasyQuantile on workstation: relative error. ## 8 Conclusions

In this paper, we discussed the problem of monitoring network latency. This problem arises naturally in the context of network services such a web browsing, voice and video calls, music and video streaming, online gaming, etc. Since a high value of latency leads to unacceptably slow response times of network services, and may increase network congestion and reduce the throughput, in turn disrupting communications and the user's experience, we discussed how to monitor this fundamental network metric. In particular, a common approach is based on tracking a specific quantile of the latencies' values, e.g., the 99 th percentile. We compared three algorithms that can track an arbitrary quantile in a streaming setting, using only a limited amount of memory, i.e., \(O(1)\) cells of memory. These algorithms are Frugal-1U, Frugal-2U, and EasyQuantile. We discussed their sequential speed of convergence on synthetic data drawn from several distributions, then we designed parallel, message-passing based versions, and we also discussed corresponding distributed versions. We proved theoretically their cost-optimality by analyzing them, and compared their parallel performance in extensive experimental tests. The results clearly show that, among the parallel algorithms we designed, the parallel version of EasyQuantile is the algorithm of choice, exhibiting very good strong and

Figure 8:6 Normal distribution on workstation: strong and weak scalability. Figure 8:7 Normal distribution on workstation: relative error. weak scaling with regard to its parallel performance, and extremely low relative error with regard to the accuracy of the quantile estimate provided. Conceptualization, M.C. and I.E. ; methodology, M.C., I.E., and M.P. ; software, M.C. and I.E. ; validation, M.P. and I.E. ; formal analysis, M.C., I.E., and M.P. ; investigation, M.C. ; resources, I.E. ; writing--original draft preparation, M.C. ; writing--review and editing, M.P. and I.E. All authors have read and agreed to the published version of the manuscript. This research received no external funding. The data used in this study were synthetically generated according to the distributions and parameters reported on Figure 8:8

We gratefully acknowledge the CMCC Foundation--Euro Mediterranean Center on Climate Changes--for providing us with access to the Juno supercomputer. The authors declare no conflicts of interest. ## References

* [PERSON] et al. (2019) [PERSON]; [PERSON]; [PERSON] [PERSON] Effects of End-to-end Latency on User Experience and Performance in Immersive Virtual Reality Applications. In _Proceedings of the Entertainment Computing and Serious Games_; [PERSON] [PERSON], [PERSON] [PERSON], [PERSON], [PERSON], [PERSON], [PERSON]; Springer International Publishing : Cham, Switzerland, 2019; pp. 57-69. * [PERSON] and [PERSON] (2021) [PERSON]; [PERSON]; [PERSON] Impact of Response Latency on User Behaviour in Mobile Web Search. In Proceedings of the 2021 Conference on Human Information Interaction and Retrieval, New York, NY, USA, 14-19 March 2021; CHIIR '21, pp. 279-283. [CrossRef]
* [PERSON] (2003) [PERSON]; [PERSON] Using Latency Quantiles to Engineer QoS Guarantees for Web Services. In _Proceedings of the Quality of Service--IWQoS 2003_; [PERSON], [PERSON], [PERSON]; Springer Berlin Heidelberg: Berlin/Heidelberg, Germany, 2003; pp. 345-362. * [PERSON] (1985) [PERSON] Random Sampling with a Reservoir. _ACM Trans. Math. Softw._**1985**, _11_, 37-57. [CrossRef]
* [PERSON] and [PERSON] (2020) [PERSON]; [PERSON] A survey of approximate quantile computation on large-scale data. _IEEE Access_**2020**, \(8\), 34585-34597. [CrossRef]
* [PERSON] et al. (2016) [PERSON]; [PERSON]; [PERSON]; [PERSON] Quantiles over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements. _VLDB J._**2016**, _25_, 449-472.