# Parallel and Distributed Frugal Tracking of a Quantile +
## 1 Introduction  
A key metric for the evaluation of a network service, related to quality of service (QoS) and network performance, is the _network latency_. Indeed, network latency may disrupt the overall user's experience: when it is sufficiently high, its impact is devastating since it leads to several problems affecting the user [1, 2]. To begin with, the user will experience unacceptably slow response times; moreover, a high network latency usually increases congestion and reduces the throughput, resulting in almost useless communications. From a technical perspective, the _message latency_ is the time required for a data packet to reach its destination, and it is the sum of several components including transmission, processing, and queuing delay. Latency fluctuations are due to factors such as the distance, the network infrastructure and congestion, the signal propagation, and the time required by network devices to process the data packets in transit. The network latency is measured as the round-trip time taken by a packet from source to destination across the network. It is measured in milliseconds (ms), and its impact on the QoS of a service depends on the specific type of service. For instance, a web server should provide a latency below 100 ms in order to guarantee a responsive browsing experience when the user loads a web page. A higher latency is the source of a perceivable delay that, besides being annoying, may lead to financial losses. In the realm of financial trading, the requirements for latency are stricter and it is not unusual for these kind of services to strive to provide an extremely low latency, measured in microseconds. A trader experiencing a delay during trades may easily decide to switch to a different service. Streaming (video or music) is another fundamental application requiring low latency; currently, a latency below 100 ms can provide a smooth streaming experience. Finally, in order to provide a good experience, voice and video calls require a latency, respectively, below 150 and 200 ms. In practice, the influence of latency onthe quality of streaming services depends on the type of streaming: one-way streaming of movies, music, etc., versus multi-way real-time streaming services, such as online gaming or conference calls. A common approach to monitoring network latency takes into account the frequently skewed distribution of latency values, and therefore specific quantiles are monitored, such as the 95 th, 98 th, and 99 th percentiles [3]. For instance, this is commonly done to precisely assess the latency of a website [4]. In order to meet customer demand and deliver good QoS values, highly requested websites (e.g., a search engine) distribute the incoming traffic load (i.e., the users' queries) among multiple web server hosts. To compute the overall latency of a website (across all of the associated web server hosts), quantiles must be precisely maintained for each host, and a distributed algorithm is necessary to aggregate individual host responses. Tracking quantiles on streams is the subject of several studies [5; 6; 7] and many different algorithms have been devised for this task [8; 9; 10; 20]. Next, we formally define rank and quantile. **Definition 1** (Rank). : _Given a multiset \(S\) with \(n\) elements drawn from a totally ordered universe set \(\mathcal{U}\), the rank of the element \(x\), denoted by \(R(x)\), is the number of elements in \(S\) less than or equal to \(x\), i.e.,_  
\[R(x):=\Big{|}\big{\{}z\in S\mid z\leq x\big{\}}\Big{|}. \tag{1}\]  
**Definition 2** (\(q\)-quantile).