arXiv:1709.07259v1 [] 21 Sep 2017

A Communication-Efficient Distributed Data
Structure for Top-k and k-Select Queries∗
Felix Biermeier
Björn Feldkord
Manuel Malatyali
Friedhelm Meyer auf der Heide
Heinz Nixdorf Institute & Computer Science Department
Paderborn University, Germany
{felixbm, bjoernf, malatya, fmadh}@mail.upb.de

Abstract
We consider the scenario of n sensor nodes observing streams of data.
The nodes are connected to a central server whose task it is to compute
some function over all data items observed by the nodes. In our case, there
exists a total order on the data items observed by the nodes. Our goal is
to compute the k currently lowest observed values or a value with rank in
[(1 − ε)k, (1 + ε)k] with probability (1 − δ). We propose solutions for these
problems in an extension of the distributed monitoring model where the
server can send broadcast messages to all nodes for unit cost. We want
to minimize communication over multiple time steps where there are m
updates to a node’s value in between queries. The result is composed of
two main parts, which each may be of independent interest:
1. Protocols which answer Top-k and k-Select queries. These protocols
are memoryless in the sense that they gather all information at the
time of the request.
2. A dynamic data structure which tracks for every k an element close
to k.
We describe how to combine the two parts to receive a protocol answering
the stated queries over multiple time steps. Overall, for Top-k queries
we use O (k + log m + log log n) and for k-Select queries O ( ε12 log 1δ +
log m + log2 log n) messages in expectation. These results are shown to be
asymptotically tight if m is not too small.

∗ This work was partially supported by the German Research Foundation (DFG) within
the Priority Program “Algorithms for Big Data” (SPP 1736).

1

1

Introduction

Consider a distributed sensor network which is a system consisting of a huge
amount of nodes. Each node continuously observes its environment and measures information (e.g. temperature, pollution or similar parameters). We are
interested in aggregations describing the current observations at a central server.
To keep the server’s information up to date, the server and the nodes can communicate with each other. In sensor networks, however, the amount of such
communication is particularly crucial, as communication has the largest impact to energy consumption, which is limited due to battery capacities [11].
Therefore, algorithms aim at minimizing the (total) communication required
for computing the respective aggregation function at the server.
We consider several ideas to potentially lower the communication used. Each
single computation of an aggregate should use as little communication as possible. Computations of the same aggregate should reuse parts of previous computations. Only compute aggregates, if necessary. Recall that the continuous
monitoring model creates a new output as often as possible.

1.1

Model

We consider the distributed monitoring model, introduced by Cormode, Muthukrishnan, and Yi in [2], in which there are n distributed nodes, each uniquely
identified by an identifier (ID) from the set {1, . . . , n}, connected to a single
server. Each node observes a stream of data items over time, i.e. at any discrete
time step t node i observes a data item dti . We assume that the data items have
a total order and denote by rank(d) the position of data item d in the sorted
ordering. Furthermore, we assume that the sorted ordering is unique, i.e. for
each data items di and dj either di ≤ dj or di ≥ dj holds.
The server is asked to, given a query at time t, compute an output f (t) which
depends on the data items dti with i = 1, . . . , n observed across all distributed
streams. The exact definition of f (·) depends on the concrete problems under
consideration, which are defined in the section below. For the solution of these
problems, we are interested in both, exact and approximation algorithms. An
exact algorithm computes the (unique) output f (t) with probability 1. An εapproximation of f (t) is an output f˜(t) of the server such that (1 − ε)f (t) ≤
f˜(t) ≤ (1 + ε)f (t) holds. We call an algorithm that provides an ε-approximation
with probability at least 1 − δ, an (ε, δ)-approximation algorithm. We say an
algorithm is correct with high probability, if for a given constant c > 1 it is
correct with probability at least 1 − n−c .
Communication Network To be able to compute the output, the nodes and
the server can communicate with each other by exchanging single cast messages
or by broadcast messages sent by the server and received by all nodes. Both
types of communication are instantaneous and have unit cost per message. That
is, sending a single message to one specific node incurs cost of one and so does
one broadcast message. Each message has a size of O B + log(n) + log(log( 1δ ))
2

bits, where B denotes the number of bits needed to encode a data item. A
message will usually, besides a constant number of control bits, consist of a data
item, a node ID and an identifier to distinguish between messages of different
instances of an algorithm applied in parallel (as done when using standard
probability amplification techniques). A broadcast channel is an extension to
[2], which was originally proposed in [13] and afterwards applied in [4, 5, 17].
Between any two time steps we allow a communication protocol to take place,
which may use a polylogarithmic number of rounds. The optimization goal is
the minimization of the communication complexity, given by the total number
of exchanged messages, required to answer the posed requests or rebuild the
data structure.
Problem Description In this work, we consider two basic problems that are
related to the rank of the data items: (1) Compute exactly (all of) the k smallest
data items observed by the nodes at the current time step t and (2) output an
(ε, δ)-approximation of the data item with rank k.
Formally, let πt denote the permutation of the node IDs {1, . . . , n} such that
πt (i) gives the index of the data item with rank i at time t, i.e. i = rank(dtπt (i) ).
First, we denote the Top-k-Problem as the output {dtπt (1) , . . . , dtπt (k) } for a given
1 ≤ k ≤ n and we consider exact algorithms for this problem. Second, we
consider the approx. k-Select Problem which is to output one data item d ∈
{dtπt ((1−ε)k) , . . . , dtπt ((1+ε)k) }. We consider (ε, δ)-approximation algorithms, i.e.
an algorithm outputs such a data item d correctly with probability at least 1−δ.
Distributed Data Structure
the following operations:

We develop a data structure which supports

UPDATE(i, d): Node i receives a new data item d.
INITIALIZE(): Set up the data structure (the nodes may already have observed data items).
REFRESH(): Is called by the server if a request is made and the data
structure is already initialized.
ROUGH-RANK(k): Returns a data item d where rank(d) ∈ [k, k · logc (n)] holds
′
with probability at least 1 − logc (n) for some suitable constants c, c′ .
ROUGH-RANK queries are used to receive an element as a basis for further computations in our protocols. We consider a distributed data stream in
our model as a sensor node observing its environment by explicitly calling an
UPDATE operation to overwrite its previous observation by a new one.

3

1.2

Our Contribution

In this paper we propose exact algorithms for the k currently lowest observed
values or approximation algorithms for a value with rank in [(1 − ε)k, (1 + ε)k]
with probability (1−δ). Our data structure is based on single-shot computations
which are of independent interest:
problem
Top-k
Top-k
Top-k
Top-k
k-Select
k-Select

type
exact
exact
exact
exact
approx.
approx.

bound
upper
upper
upper
lower
upper
lower

(total) comm.
O (k · log(n))
k + log(n) + 1
O (k + log(n))
k + Ω(log(n))
O ( ε12 log( δ1 ) + log(n))
Ω(log(n))

comm. rounds
O (k · log(n))
O (k + log(n))
O (log( nk ))
/
O (log( nk ))
/

Reference
[4]
Section 2
Section 3.2
Section 5
Section 3.2
Section 5

Table 1: Summary of results for single-shot computations.
With notion of the data structure this relates to the results as presented in
Table 2.
operation
INITIALIZE
REFRESH
UPDATE
ROUGH-RANK

(total) comm.
O (log(n)), Ω(log(n))
O (log(m)), Ω(log(m))
amortized
0

comm. rounds
O (log(n))
O (log(n))
1
0

Reference
Section 4.1
Section 4.2
Section 4
Section 4

Table 2: Summary of results using our new data structure.

In Section 4.3 we describe how to combine the one-shot computations with
the given data item from the ROUGH-RANK operation supported by our data
structure. This leads to the overall bound of Θ(k + log(m) + log(log(n))) messages in expectation for Top-k queries. The bound on the number of messages
is asymptotically tight if m ≥ log(n) holds where m denotes the number of
UPDATEs since the last query. For k-Select queries and applying the same
combination as above, this protocol uses Θ ε12 log( 1δ ) + log(m) + log2 (log(n))
messages in expectation, where the bound on the number of messages is asymptotically tight if m ≥ loglog(log(n)) (n) holds.
Furthermore, we parameterize our algorithms such that it is possible to
choose a trade-off between the number of messages used and the number of
communication rounds, i.e. time, used to process the queries.

1.3

Related Work

Cormode, Muthukrishnan, and Yi introduce the Continuous Monitoring Model
[2] with an emphasis on systems consisting of n nodes generating or observing
distributed data streams and a designated coordinator. In this model the coordinator is asked to continuously compute a function, i.e. to compute a new
4

output with respect to all observations made up to that point. The objective
is to aim at minimising the total communication between the nodes and the
coordinator. We enhance the continuous monitoring model (as proposed by
Cormode, Muthukrishnan, and Yi in [13]) by a broadcast channel. Note, that
we are not strictly continuous in the sense that we introduce a dynamic data
structure which only computes a function, if there is a query for it. However,
there is still a continuous aspect: In every time step, our data structure maintains elements close to all possible ranks in order to quickly answer queries if
needed.
An interesting area of problems within this model are threshold functions:
The coordinator has to decide whether the function value (based on all observations) has reached a given threshold τ . For well structured functions (e.g.
count-distinct or the sum-problem) asymptotically optimal bounds are known
[2, 13]. Functions which do not provide such structures (e.g. the entropy [1]),
turn out to require much more communication volume.
A related problem is considered in [12]. In their work, Babcock and Olston
consider a variant of the distributed top-k monitoring problem: There is a set
of objects {O1 , . . . , On } given, in which each object has a numeric value. The
stream of data items updates these numeric values (of the given objects). In case
each object is associated with exactly one node, their problem is to monitor the
k largest values. Babcock and Olston have shown by an empirical evaluation,
that the amount of communication is by an order of magnitude lower than that
of a naive approach.
A model related to our (sub-)problem of finding the k-th largest values, and
exploiting a broadcast channel is investigated by the shout-echo model [14, 15]:
A communication round is defined as a broadcast by a single node, which is
replied by all remaining nodes. The objective is to minimise the number of
communication rounds, which differs from ours.

2

One shot computation: Top-K

In this section we present an algorithm which identifies all data items with rank
at most k currently observed by the sensor nodes. Note that when we later apply
this protocol for multiple time steps, not all sensor nodes might participate. In
this section, we denote by N the number of participating nodes.
Our protocol builds a simple search-tree-like structure based on a height
the nodes draw from a geometric distribution. Afterwards, a simple strategy
comparable to an in-order tree walk is applied. In order to identify the smallest
data item this idea is implemented as follows: The protocol draws a uniform
sample of (expected) size φ1 and broadcasts the smallest data item. Successively,
the protocol chooses a uniform sample until the smallest item is identified. In
this description, each drawing of a sample corresponds to consider all children
of the current root of the search tree and then continue with the left-most child
as the new root.
The protocol is given a maximal height hmax for the search tree which corre5

sponds to the number of repetitions of the protocol described above. We define
a specific value for hmax in Theorem 2.3. Furthermore, the algorithm is given a
parameter φ which defines the failure probability of the geometric distribution.
Algorithm 1 Top-k Protocol (φ, hmax )
Initialization()
Top-k-Rec(ℓ, u, h)
1. Each node i draws a ran1. If h = 0 then
dom variable hi , i.i.d. from
2.
if |S| = k then return S,
a geometric distribution
3.
Else end recursion
with p = 1 − φ
4. Server probes sensor nodes i with
ℓ < di < u and hi ≥ h
2. Server defines ℓ := −∞,
Let r1 < . . . < rj be the responses
u := ∞, h := hmax and
5. If there was no response then
S←∅
6.
Call Top-k-Rec(ℓ, u, h − 1)
7.
Else
3. Call Top-k-Rec(ℓ, u, h)
8.
Call Top-k-Rec(ℓ, r1 , h − 1)
4. Raise an error, if |S| < k
9.
S ← S ∪ r1
10. For i = 1 to j − 1 do
11.
Call Top-k-Rec(ri , ri+1 , h−1)
12.
S ← S ∪ ri+1
13. Call Top-k-Rec(rj , u, h − 1)
The algorithm starts by drawing a random variable hi from a geometric
distribution, i.e. Pr[hi = h] = φh−1 (1 − φ). We discuss the choice of φ at the
end of this section. Note that φ enables a trade off between the number of
messages sent in expectation and communication rounds used.
The protocol can be implemented in our distributed setting by having the
server broadcast the values ℓ, u, and h such that each node with the corresponding height values and data items responds. Note, the variables r1 , . . . , rj used
in Steps 8, 9, 11, 12, and 13 refer to responses of the current call of Top-k-Rec.
Analysis
In the following we show that the expected number of messages used by the
Top-k Protocol is upper bounded by k + 1−φ
φ · log1/φ (N ) + 1 in Theorem 2.3.
Afterwards, an upper bound of O (φ · k + hmax ) on the number of communication rounds is presented in Lemma 2.4. Defining φ := 1/2 the bound on the
communication translates to a tight bound of k + log(n) + 1 in Corollary 2.5
complemented by a simple lower bound of k + Ω(log(n)) in Section 5.
We show an upper bound on the communication used by the Top-k Protocol
analyzing the expected value of a mixed distribution. The analysis works as
follows: We sort the nodes by their rank and determine the number of nodes
with height ≤ h before the first node with a height > h in this ordering by a
geometric-sequence in Definition 2.1. For each height h, this number can then

6

be used to determine the number of nodes which send a message on height
h, which we model by a geocoin-experiment in Definition 2.2. Note that this
analysis turns out to be very simple since independence can be exploited in a
restricted way and leads to a proper analysis with respect to exact constants.
Definition 2.1. We call a sequence G = (G1 , . . . , Gm ) of m random experiments a geometric-sequence, if each Gh is chosen
from a geometric distribution
P
h
:=
:=
φ
.
We
denote
its
size(G)
with pgeo
G
and say it covers all nodes,
h
h
h
if size(G) ≥ N .
For the analysis, we choose a fixed length of m := log1/φ (N ) and modify G
to G′ = (G1 , . . . , Gm−1 , N ) such that G′ covers all nodes with probability 1.
Based on a given geometric-sequence, we define a sequence describing the
number of messages send by the nodes on a given height. We take the number
of nodes Gi as a basis for a Bernoulli experiment where the success probability
is the probability a node sends a message on height i. This is Pr[h = hi | h ≤
h−1
(1−φ)
hi ] = φ 1−φ
.
h
Definition 2.2. We denote a geocoin-experiment by C = (C1 , . . . , Cm ) of ranh−1
(1−φ)
),
dom variables Ch which are drawn from Binom(n = Gh , pbin
= φ 1−φ
h
h
i.e. Ch out of Gh successful coin tosses where each coin toss is successful with
probability pbin
h .
Theorem 2.3. Let N > k and hmax ≥ log1/φ (N ) hold. The Top-k Protocol
uses at most k + 1−φ
φ log1/φ (N ) + 1 messages in expectation.
Proof. The probability to send a message of a node v within the Top-k is 1. It
log1/φ (N ) + 1.
remains to show that the overhead is bounded by 1−φ
φ
The number of messages sent by Algorithm 1 (excluding the k nodes observing the k smallest data items) is upper bounded by a geocoin-experiment C. Let
H := log1/φ (N ). For h < H we use that the geometric distribution is memory h−1

φ
(1−φ)
bin
h
less and hence E[Ch ] = (1−pgeo
)·(p
+E[C
])
=
(1−φ
)·
+
E[C
]
.
h
i
h
h
h
1−φ
This can simply be rewritten as E[Ci ] = (1 − φ)/φ.
For i ≥ H we bound the number of messages by the total number of nodes
with height at least H. These can be described as the expectation of a Bernoulli
experiment with N nodes and success probability φH−1 and hence E[C≥H ] ≤
φH−1 · N = 1/φ.
P

P
H −1
1−φ
log1/φ (N ) + 1.
In total, we get h E[Ch ] =
i=h E[Ci ] + E[C≥H ] ≤ φ
Lemma 2.4. The Top-k Protocol needs O (φ · k + hmax ) communication rounds
in expectation.

Proof. We structure the proof in two steps: First, we analyse the number of
rounds used to determine the minimum, and second, the number of communication rounds used to determine the Top-k.
Observe, that the algorithm uses a linear amount of steps (linear in hmax ),
until it reaches h = 1, after which the minimum is found. Afterwards in each
7

step the algorithm recursively probes for nodes successively larger than the
currently largest values, that are added to the output set S. Note, that by the
analysis in Theorem 2.3, the number of nodes that send a message in expectation
in each round is (1 − φ)/φ (for h < log1/φ (N )). Thus, in each communication
round there are Ω( φ1 ) nodes in expectation that send a message, such that after
O (φ · k) rounds in expectation the Top-k Protocol terminates.
Note that our bounds describe a trade off between the number of messages
and communication rounds, where the number of messages decreases with a
small success probability 1−φ. Intuitively speaking, this stems from more larger
resulting height values such that the search structure has a smaller breadth.
Corollary 2.5. For N = n, φ := 12 , and hmax := log(n), the Top-k Protocol
uses an amount of k + log(n) + 1 number of messages in expectation and O (k +
log(n)) communication rounds.

3

One Shot Computation: Approximate k-Select

In this section we present an algorithm which gives an (ε, δ)-approximation for
the k-Select Problem, i.e. a data item d is identified with a rank between (1−ε)k
and (1 + ε)k with probability at least 1 − δ.
In Section 3.1, we introduce an algorithm which identifies a data item with
rank Θ(k). This is done to reduce the number of messages for the algorithm
proposed in Section 3.2 which uses a standard sampling technique to achieve
the desired approximation.

3.1

Constant Factor Approximation

The following algorithm employs a similar strategy as Algorithm 1. However,
the protocol terminates and outputs a data item as soon as the targeted height
of hmin is reached. This data item is one of the responses on height hmin ,
dependent on the value of φ. Note that it may not be sufficient to output the
smallest value, since the number of responses may be very large if φ is small.
We show that Algorithm 2 outputs a data item with a rank larger than k
and smaller than 42 k with constant success probability in Lemma 3.1. Furthermore, we state that Algorithm 2 determines a data item which is at most
by a polylogarithmic factor larger than the expectation with high probability in
Lemma 3.2. We need this result later when reusing the protocol in Section 4.
An upper bound on the number of used messages is presented in Lemma 3.3.
We shortly state how to amplify the success probability to 1 − δ ′ for a given
δ ′ > 0 in Theorem 3.4.
Lemma 3.1. The CoFaSel Protocol outputs a data item d with rank(d) ∈
[k, 42k] with probability at least 0.6.
Proof. The algorithm outputs the (1/φ)α smallest data item d the server gets as
a response on height h = hmin . To analyze its rank simply consider the random
8

Algorithm 2 CoFaSel(hmax , φ, k)

(ConstantFactorSelect)

1. Each node i defines a random variable hi , i.i.d. drawn from
a geometric distribution with p = (1 − φ), and redefines hi :=
min{hi , hmax }.
2. Server defines dmin := ∞.

⊲ ∀ data items d: ∞ > d

3. Server defines 0 < α < 1, s.th. ⌊log1/φ (7k)⌋ = log1/φ (7k) − α ∈ N holds.
4. for h := hmax to hmin = log1/φ (7 k) − α + 1 do
5.

Server probes all nodes i with di < dmin and hi = h.

6.

Let r1 < r2 < . . . < rj be the responses, ordered by their values.

7.

If h > hmin then Server redefines dmin := r1 else dmin := r(1/φ)α .

8. Output dmin
number X of nodes i that observed smaller data items di < d. The claim follows
by simple calculations: (i) Pr[X < k] ≤ 15 and (ii) Pr[42k > X] ≤ 51 .
The event that X is (strictly) smaller than k holds, if there are (1/φ)α out
of k nodes with a random height at least hmin . Let X1 be drawn by a binomial
distribution Bin(n = k, p = φhmin −1 ). It holds E[X1 ] = k · φhmin −1 = 17 · ( φ1 )α .
Then, Pr[X < k] ≤ Pr[X1 ≥ ( φ1 )α ] = Pr[X1 ≥ (1+6) 7φ1α ] ≤ exp(− 13 7φ1α 62 ) ≤ 51 .
On the other hand, the event that X is (strictly) larger than 42k holds, if
there are less than (1/φ)α out of 42k nodes with a random height of at least
hmin . Let X2 be drawn by a binomial distribution Bin(n = 42k, p = φhmin −1 ).
It holds E[X2 ] = (42k)φhmin −1 = (42k)(7k)−1 φ−α = φ6α . Then, Pr[X > 42k] ≤
Pr[X2 < φ1α ] = Pr[X2 < (1 − (1 − 16 )) φ6α ] ≤ exp(− 12 ( φ6α (1 − 61 )2 ) ≤ exp(− 25
12 ) ≤
1
5.
Lemma 3.2. For a given constant c > 8 there exist constants c1 , c2 > 1, such
that the CoFaSel Protocol as given in Algorithm 2 outputs a data item d with
a rank in [log c1 (n) · 7k, log c2 (n) · 7k] with probability at least 1 − n−c .
Proof. We use the same simple argumentation as in Lemma 3.1, but instead
consider a larger amount of nodes that participate in the binomial experiment.
Let X denote the rank of the data item d which is identified by Algorithm 2,
and let Y be drawn by Bin(n = 7k logc (n), p = φhmin −1 ). Observe that E[Y ] =
7k · logc (n) · (φhmin −1 ) = 7k · logc (n)(7k)−1 φ−α = logc (n)φ−α holds and thus,
Pr[X > 7k logc (n)] ≤ Pr[Y < φ1α ] ≤ Pr[Y < (1 − (1 − logc1(n) )) logc (n)φ−α ] ≤
exp(− 21 logc (n)φ−α (1 −

1
2
logc (n) ) )

1

≤ exp(− 81 logc (n)) ≤ n− 8 c .

Lemma 3.3. Let N > k and hmax ≥ log1/φ (N ) hold. The CoFaSel Protocol presented in Algorithm 2 uses an amount of at most O ( φ1 (log1/φ ( N
k ) + 1))
messages in expectation.
9

Proof. Consider one instance of CoFaSel and applying arguments from Theorem 2.3,
the algorithm uses φ1 messages in expectation for each iteration of Steps 4 to 6.
Taking hmax − hmin + 1 repetitions of Steps 4. to 6., and an expected amount
of φ1 messages per repetition into account, the total number of messages follows
as claimed.
We apply a standard boosting technique, i.e. we use O (log( δ1′ )) independent
instances of Algorithm 2, and consider the median of the outputs of all instances
to be the overall output. We denote this amplified version of CoFaSel by
CoFaSelAmp. Thus, an output in the interval [k, 42 k] with probability at
least 1 − δ ′ is determined.
Since we run the O (log( δ1′ )) instances in parallel, and the server is able
to process all incoming messages within the same communication round, the
number of communication rounds does not increase by this extension of the
protocol. These simple observations lead to the following theorem summarizing
a first result for the k-select problem:
Theorem 3.4. Let N > k and hmax ≥ log1/φ (N ) hold. Let δ ′ be a given constant. The algorithm CoFaSelAmp determines a data item d with rank at least
k and at most 42k with probability at least 1 − δ ′ using O ( φ1 log1/φ ( Nk ) log( δ1′ ))
messages in expectation and hmax − hmin + 2 communication rounds.

3.2

Approximate k-Select

In this section we propose an algorithm which is based on the algorithm from the
previous section. Here, we aim for an (ε, δ)-approximation of the k-Selection
problem for a single time step. Using the approximation given by CoFaSelAmp, which gives a data item d with a rank between k and 42k with probability at least 1 − δ ′ , a simple standard sampling strategy is applied afterwards.
Note that only those nodes take place in this strategy which observed a data
item di smaller than d.
Algorithm 3 Approx. k-Select Protocol ApproKSel(k, φ, ε, δ ′ , δ, hmax )
1. Call CoFaSelAmp(hmax , φ, k, δ ′ ) and obtain data item d.
2. Each node i with di < d:
3.
4.


Toss a coin with p := min 1, kc Sε,δ .
On success send di to the server.

5. The server sorts these values and outputs dK , the p · k-th smallest item.
In the following, we show that Algorithm 3 is an (ε, δ)-approximation of the
k-Selection protocol in Theorem 3.5. We discuss a possible choice of parameters
in Corollary 3.6.

10

Theorem 3.5. Let N > k and hmax ≥ log1/φ (N ) hold. The Approx. k-Select
Protocol selects data item dK with rank in [(1 − ε) k, (1 + ε) k] with probability
c
at least 1 − δ using O ((1 + logk(n) δ ′ )Sε,δ + φ1 log1/φ ( Nk ) log( δ1′ )) msg. in exp. and
hmax − hmin + 3 comm. rounds.
Proof. From Theorem 3.4 we get that the CoFaSelAmp protocol uses at most
O ( φ1 log1/φ ( Nk ) log( δ1′ )) messages on expectation and runs for hmax − hmin + 2
communication rounds. The remaining steps of Algorithm 3 need only one communication round and thus the stated bound on the communication rounds follows. We omit the proof for the correctness of the algorithm, i.e. with demanded
probability the k-th smallest data item is approximated, since it is based on a
simple argument using Chernoff bounds.
It remains to show the upper bound on the number of messages used. Formally, we apply the law of total expectation and consider the events that the
CoFaSelAmp protocol determined a data item d with rank k ≤ rank(d) ≤ 42k
and the event rank(d) > 42k.
K)
Sε,δ )
Observe that the sampling process in steps 2 and 3 yields O ( rank(d
k
number of messages in expectation. Consider the event CoFaSelAmp determined a data item d with rank k ≤ rank(d) ≤ 42k. Then, the Approx. k-Select
Protocol uses O (Sε,δ ) messages in expectation. Now consider the event CoFaSelAmp determined a data item d with d > 42 k. We upper bound the
numberof messages used for this case by the rank of the given value r: It
c
uses O logk(n) Sε,δ messages in expectation. Since the probability for this
event
upper bounded
by δ ′ , the conditional expected number of messages is
 is

logc (n)
O
Sε,δ · δ ′ .
k

For the sake of self containment we propose a bound which considers all
nodes to take part in the protocol (N = n). Note, that the CoFaSelAmp
protocol outputs a value with rank smaller than 7k · polylog (n) w.h.p. (c.f.
Lemma 3.2).
Corollary 3.6. Let c be a sufficiently large constant. Furthermore, let N = n,
φ := 21 , hmax := log n, and δ ′ := logc1(n) . The protocol uses an amount of at
most O (Sε,δ + log(n) log(log(n))) messages in expectation and log( nk ) rounds of
communication.
This represents the case that a small number of messages and a large number
of communication rounds are used. This observation is complemented by a
lower bound of Ω(log(n)) in Section 5. Note, that this bound can be reduced to
O (Sε,δ +log(n)) by running one instance of CoFaSel until h′min := ⌈log(7k)⌉+c
and denote the output (i.e. the smallest data item) as d. The Approx. k-Select
Protocol is then applied only on nodes that observed data items smaller than d.
Corollary 3.7. Let N = n, φ := 21 , hmax := log n, k ′ := 2k, ǫ := 12 and
δ ′ := logc1(n) . The protocol uses O (k + log(n)) messages in expectation to solve
the Top-k-Problem.
11

4

Multiple Time Step Computation:
A Fully Dynamic Distributed Data Structure

In this section we consider computations of Top-k or approx. k-Select for multiple time steps. We use a dynamic data structure to keep rough information such
that a required computation can be executed more efficiently. The main part of
this section focuses on computing an element with rank close to k utilizing our
data structure. The final results for answering the queries on the basis of this
element are described in Section 4.3.
Our basic idea is to maintain a structure similar to the trees (to be more precise, only the left-most path) used to identify the (approximately) k’th smallest
items in the previous chapters. The data structure maintains the rough rank
sketch which is defined as follows:
Definition 4.1 (Rough Rank Sketch (RRS)). A data structure for the approximate k-select problem fulfills the RRS property if a request for the data item of
rank k will be answered with an item of rank in [k, logc (n) · k] with probability
at least 1 − log−c (n).
We divide the ranks 1, . . . , n into classes. The goal is that a data item of
each class (representative) is contained in our data structure. The height of a
class represents the expected maximum height found within this class, such that
our representative will have a height value within the noted bounds.
Let H := log1/φ (log(n)). The idea of classes is captured in the following
definition:
Definition 4.2. Let κ be sufficiently large. A Class Cℓt consists of all data
items dtj with rank(dtj ) ∈ [logℓ8κ (n), log(ℓ+1)8κ (n)). We denote by h(Cℓt ) =
(ℓ8κH , (ℓ + 1)8κH ] the height of the class Cℓt .
By abuse of notation we introduce dti ∈ Cℓt which shortens rank(dti ) ∈ Cℓt .
We divide each class into sub-classes as follows:
t
,
Definition 4.3. Let κ be defined as before. We denote by a sub class Cℓ,τ
t
t
with τ ∈ {0, . . . , 3}, the set of data items di with a rank rank(di ) between
t
t
) = ((ℓ8κ +
logℓ8κ+2τ κ (n) and logℓ8κ+(2τ +2)κ (n). The height of Cℓ,τ
is h(Cℓ,τ
(2τ + 1)κ)H , (ℓ8κ + (2τ + 3)κ)H ].

We omit the time step t in our notation whenever it is clear from the context.
Definition 4.4. The data items in a class Cℓ are well-shaped, if for each
data item di with rank(di ) ∈ [logℓ8κ+2τ κ (n), logℓ8κ+(2τ +2)κ (n)] it holds hi ≤
(ℓ8κ + (2τ + 3)κ)H .

4.1

Correctness of INITIALIZE

We start by analyzing the outcome of the INITIALIZE operation. In this, we
show that a class is well-shaped with sufficiently large probability in Lemma 4.5
12

Algorithm 4 SeleMon(φ)
[Select and Monitor]
INITIALIZE() [Repeat until all classes are filled, i.e. ∀ℓ ∃aℓ ∈ Sℓ,1 , rℓ ∈ Sℓ,2 ]
1. Call CoFaSel (φ, hmax = log1/φ n, k = 1) (Algorithm 2), and keep a
data structure DS with all (hi , di ) pairs, where for each hi the smallest
response di is kept.
2. Assign data item di with height hi to its sub class Sℓ,τ ′ , if hi ∈ h(Cℓ,τ ′ )
holds.
3. Choose aℓ ∈ Sℓ,1 and rℓ ∈ Sℓ,2 uniformly at random.
UPDATE(i, d) [Executed by node i]
1. Update dti by dt+1
= d, delete (dti , hti ) from DS (if it was in DS).
i
2. If di = aℓ or di = rℓ or (hi ∈ [h(aℓ ), h(rℓ )] and di < aℓ )
then delete all (hj , dj ) pairs from DS, where dj ∈ Sℓ holds.
3. Draw a new value from the geometric distribution with p = (1 − φ) and
redefine hi := min{hi , hmax }.
REFRESH() [Repeat until all classes are filled, i.e. ∀ℓ ∃aℓ ∈ Sℓ,1 , rℓ ∈ Sℓ,2 ]
1. define t := t + 1
2. Determine level ℓ such that all classes Cℓ′ , ℓ′ > ℓ are filled,
more formally ∀ℓ′ > ℓ, Sℓ,1 6= ∅ ∧ Sℓ,2 6= ∅.
3. Determine maximal height h of all nodes i that observed an UPDATE
since the last INITIALIZE or REFRESH operation. Let ℓ′′ be the level
with h ∈ h(Cℓ′′ ).
Define ℓ := max(ℓ, ℓ′′ ).
4. Call INITIALIZE() (only on sensor nodes i with di < rℓ )
ROUGH-RANK(k)
1. Determine ℓ such that k ∈ Cℓ−1 holds.
2. Output representative rℓ ∈ Sℓ,2 .

⊲ k denotes a rank

and argue that the data structure yields a RR-Sketch in Theorem 4.7, afterwards.
Lemma 4.5. Let ℓ ∈ N. After an execution of INITIALIZE, the class Cℓ is
well-shaped with probability at least 1 − log−c (n), for some constant c.
Proof. Fix a sub class Cℓ,τ and consider the data items di with rank(di ) ∈
Cℓ,τ = [logℓ8κ+2τ κ (n), logℓ8κ+(2τ +2)κ (n)]. The sub class admits the well-shaped
property, if each data item has a height of at most h := (ℓ8κ + (2τ + 3)κ)H .
To this end, we upper bound the probability that there is a data item with a
height of at least h by applying union bound as follows:


Pr[∃di ∈ Cℓ,τ : hi > h] ≤ logℓ8κ+(2τ +2)κ (n) − logℓ8κ+(2τ )κ (n) · φh
≤ logℓ8κ+(2τ +2)κ (n) · log−(ℓ8κ+(2τ +3)κ) (n) ≤ log−κ (n)

Since there are 4 sub classes in class Cℓ , the probability that there exists a data
13

item which prevents the class to be well shaped is upper bounded by 4 log−κ (n)
applying union bound once again.
Lemma 4.6. Consider a sub class Cℓ,τ ′ , with τ ′ ∈ {1, 2}. There is a data item
di ∈ Cℓ,τ ′ with hi > (ℓ8κ + (2τ ′ + 1)κ)H with high probability.
Proof. Recall that for a fixed data item di and sensor node i the probability for
hi > h is φh . Here we simply upper bound the probability that each data item
in the sub class has a height of at most h as follows:

|Cℓ,τ ′ |
′
Pr[∀di ∈ Cℓ,τ ′ : hi ≤ (ℓ8κ + (2τ ′ + 1)κ)H ] ≤ 1 − φ(ℓ8κ+(2τ +1)κ)H

logℓ8κ+(2τ ′ +2)κ (n)−logℓ8κ+(2τ ′ )κ (n)
−(ℓ8κ+(2τ ′ +1)κ)
≤ 1 − log
(n)
  21 logκ (n)
κ−1
1
1
≤
≤ n− 2 log(e) log (n) ≤ n−c ,
e

for some constant c.
Theorem 4.7. After execution of INITIALIZE for each rank k exists a data
item in the data structure with rank between k and k · logc (n) with probability at
′
least 1 − log−c (n) for constants c, c′ .
Proof. First consider a fixed class Cℓ for a fixed ℓ ∈ N. Based on Lemma 4.5
we can show that the distribution
of the random heights is well-shaped with
∗
probability at least 1 − log−c (n) for a constant c∗ . Now, with high probability
there is a data item with such a height for sufficiently large κ and n due to
Lemma 4.6. We may in fact
choose c∗ such that the probabilities for both to
−c∗
occur is at least 1 − log (n). These observations together show that there is
a data item d′τ identified and stored in DS and thus, for each request k ∈ Cℓ−1
the algorithm has identified a representative in Cℓ as a response with a rank
only by a polylogarithmic factor larger than k.
Furthermore, note that there are at most log(n) number of classes. The argument stated above applied to each class leads to the desired result, where (apply∗
ing union bound) also shows the desired success probability of 1 − log−(c −1) (n).
Now we have shown that the Rough Rank Sketch is calculated by executing INITIALIZE with certain probability. To analyze the number of messages
in expectation and the number communication rounds we refer to Lemma 3.3
and Theorem 3.4, respectively. Since INITIALIZE is strongly based on the CoFaSel protocol, similar arguments hold for this section, again. However, note
that the repetitions of the algorithm to obtain representatives aℓ and rℓ for each
level ℓ and thus for each class Cℓ is not straight forward. A complete recomputation from scratch until all representatives are obtained introduces a factor
of log∗ (n) to the communication costs and rounds. For this simply observe
that there are at most log(n) different classes Cℓ , for which However, here only
14

for those levels the CoFaSel protocol is called, where aℓ and rℓ is not known
leading to additional constant factor overhead (in expectation).

4.2

Correctness of REFRESH

In the previous subsection we have shown that the algorithm INITIALIZE computes a Rough Rank Sketch for a fixed time step. In this section we show that
the REFRESH method preserves and / or rebuild parts of the data structure
such that a Rough Rank Sketch is achieved after m UPDATES took place. We
analyze two different scenarios and analyze the probability of the scenario to
occur: The representative of the class itself is UPDATED and thus, the class
gets deleted and the case that the representative does not get an UPDATE, but
the rank does not reflect the situation correctly at the next time step t + 1.
4.2.1

UPDATE to a representative

We analyze the probability that the alarm aℓ or the representative rℓ of a class
Cℓ is updated and thus, the class gets deleted from the data structure. This
is okay, if there are sufficiently many UPDATEs, i.e. m is sufficiently large.
However, if m is small compared to the number of data items sub classes Cℓ,1
and Cℓ,2 consists of, the probability to choose exactly aℓ or rℓ for an UPDATE
and thus delete from the data structure is small, as Lemma 4.8 states. The
proof can be found in the appendix.
Lemma 4.8. Let m be the number of UPDATE operations since INITIALIZE
or REFRESH is called. Let Cℓ be a class with m < logℓ8κ (n). The representative
of Ci did not get an update with probability at least 1 − log−c (n), for a constant
c.
Proof. Recall that the algorithm deletes the element di from DS if UPDATE(i, d)
is called for an arbitrary d. The probability that the representative is updated
is maximized if the UPDATE operations occur on m different nodes.
′
′
The size of Cℓ,τ ′ is at least logℓ8κ+(2τ +2)κ (n) − logℓ8κ+2τ κ (n) which is
′
larger than 21 logℓ8κ+(2τ +2)κ (n) and m ≤ M = logℓ8κ+1 (n). The probability
for Algorithm 4 to randomly choose one of these nodes as a representative is
upper bounded by the term 2 log−2κ (n) ≤ log−c (n).
4.2.2

Push representative out of class

We want to estimate the probability that some representative di from our data
structure was in Cℓt but not in Cℓt+1 .
We start our analysis with a result on the rank of a data item, given the
randomly drawn height in Lemma 4.9. Afterwards, we show in Lemma 4.10
that the representative of Cℓt is still in Cℓt+1 , if m is not too large. However,
if the number of updates is large, we analyze that the representative is deleted
from DS in Lemma 4.11 with sufficiently large probability. We conclude that

15

the desired properties of the data structure are restored after a REFRESH
operation (Theorem 4.12).
Lemma 4.9. Fix a time t. Consider a data item di ∈ DS and let hi ∈ h(Cℓ,τ ′ )
be the height of data item di . It holds di ∈ Cℓ,τ ′ with high probability.
Proof. We can apply a Chernoff argument to bound the probability that the
rank of a given data item is of a specific range as follows: Consider data item di
and fix the height hi node i has drawn randomly. Since di ∈ DS holds, di is the
smallest data item among all data items with height hi . Intuitively speaking,
the rank of the data item with height hi is simply the number of repetitions
of the random experiment until there is a ’success’, meaning the height hi is
drawn.
′
We bound the probability for the events rank(di ) < logℓ8κ+2τ κ (n) denoted
′
by E1 and rank(di ) > logℓ8κ+(2τ +2)κ (n) denoted by E2 .
′

Pr[E1 ] = Pr[∃i : rank(di ) < logℓ8κ+2τ κ (n) ∧ hi ∈ h(Iℓ )]
′

≤ Pr[∃i : rank(di ) < logℓ8κ+2τ κ (n) ∧ hi > (ℓ8κ + (2τ ′ + 1)κ)H ]
To apply a Chernoff bound consider the expected number X of ’successful’
coinflips, where hi > (ℓ8κ + (2τ ′ + 1)κ)H is a successful coin flip:
′

γX := E[X] = logℓ8κ+2τ κ (n) · φ(ℓ8κ+(2τ

′

+1)κ)H

= log−κ (n)

Now consider the probability that there is a node with a coin success and a
small rank to upper bound Pr[E1 ] as follows:
Pr[X > (1 + (logκ (n) − 1))γX ] ≤ exp(−

κ−2
1
1
· (logκ (n))2 γX ) ≤ n− 12 log (n)
12

This can be upper bounded by n−c for κ ≥ 3 and sufficiently large n.
The argument for Pr[E2 ] follows similar ideas:
Pr[E2 ] = Pr[∀i : rank(di ) < logℓ8κ+(2τ

′

+2)κ

(n) ⇒ hi < (ℓ8κ + (2τ ′ + 1)κ)H ]

Now consider the expected number Y of ’successful’ coin flips, where hi ∈ h(Iℓ )
is a successful coin flip:
γY = E[Y ] ≤ logℓ8κ+(2τ

′

+2)κ

(n) · φ(ℓ8κ+(2τ

′

+1)κ)H

= logκ (n)

Now consider the probability that there is no node with a coin success:
κ−2
1
1
1
Pr[E2 ] ≤ Pr[Y < (1 − )γY ] ≤ exp(− · γY ) ≤ n− 12 log (n) ≤ n−c ,
2
12

with κ ≥ 3 and sufficiently large n.
Lemma 4.10. Fix an ℓ with m < logℓ8κ (n). Let t0 be the time step INITIALIZE was called and t − t0 ≤ log(n) hold. If at every time t′ ∈ [t0 , t] it holds
mt′ < logℓ8κ (n), then the representative of Cℓt0 is a valid representative of Cℓt
(w.h.p.).
16

t0
Proof. Fix the sensor node i which observed di = rℓ . Recall that rℓ ∈ Cℓ,2
holds. Now define the following: Denote by m1 the number of nodes j that
observed a data item dtj0 < di at time t0 and dtj > dj at time t. Additionally, let
M := log(n) · logℓ8κ (n) = logℓ8κ+1 (n) be the upper bound on the total number
of UPDATE operations since the last INITIALIZE operation.
We first consider the case that m1 is maximal, i.e. m1 = M . Recall that
rank(dti0 ) = rank(rℓ ) ∈ Cℓ,2 holds with high probability due to Lemma 4.9,
i.e. rank(dti0 ) ≥ logℓ8κ+2κ (n) holds. This leads to the simple observation that
rank(dti ) ≥ logℓ8κ+2κ (n) − M ≥ logℓ8κ (n) holds with high probability.
The argument for a maximal m2 is analog, the claim follows.

Lemma 4.11. Fix an ℓ with m ≥ logℓ8κ (n). Let t0 be the time step INITIALt
IZE was called and t − t0 ≤ log(n) hold. If rℓ ∈ Cℓ,2
is no longer in Cℓt+1 the
protocol deletes rℓ with high probability.
t
t
Proof. Fix aℓ ∈ Cℓ,1
and rℓ ∈ Cℓ,2
. Consider two cases: (1) there are (up to)
m UPDATES such that the rank of rℓ increases and (2) (up to) m UPDATES
such that the rank of rℓ decreases.
t
t
(1) Recall that rℓ ∈ Cℓ,2
holds, where di ∈ Cℓ,2
if for the rank of data item di
ℓ8κ+4κ
ℓ8κ+6κ
it holds rank(di ) ∈ [log
(n), log
(n)]. The ranks of the data items in
class Cℓ are upper bounded by logℓ8κ+8κ (n). Thus, there are at least a number
of logℓ8κ+8κ (n) − logℓ8κ+6κ (n) ≫ 12 logℓ8κ+8κ (n) data items which observe an
UPDATE and flip a coin due to the UPDATE algorithm. By the same argument
as in Lemma 4.5 and Lemma 4.6, there is one data item dnew with a height
strictly larger than the height of the data item aℓ (with high probability). Thus,
the data items aℓ and rℓ get deleted from DS with high probability.
(2) For this case we argue that it is unlikely that the data item rℓ which was a
representative at time t has a rank smaller than logℓ8κ (n) at time t + 1 without
t
observing an update of data item aℓ : Recall, that rℓ ∈ Cℓ,2
, i.e. rank(rℓ ) ≥
ℓ8κ+4κ
ℓ8κ+4κ
ℓ8κ+2κ
log
(n). There have to be at least log
(n) − log
(n) UPDATE
calls such that rℓ is incorrectly in Cℓt+1 (if it is not deleted). In case aℓ ∈ Cℓ,1
holds, the respective sensor node observes an UPDATE to the data item aℓ with
high probability followed by a deletion of rℓ , concluding the proof.

Theorem 4.12. After each REFRESH operation the Rough Rank Sketch is
restored, i.e. for each rank k there exists a data item d in the data structure DS
as defined in Algorithm 4 with rank between k and k · logc (n) with probability at
′
least 1 − log−c (n).
Proof. First, observe that this property holds after the INITIALIZE operation
due to Theorem 4.7. It remains to show that this property is preserved or
refreshed after an UPDATE operation. We argue for an arbitrary but fixed class
Cℓ . Consider the following case distinction: (1) The representative rℓ of Cℓ is
updated and thus, the class gets completely rebuilt and (2) the representative
rℓ of Cℓ is not updated.
[Representant rℓ ∈ Cℓ is updated] In this case, each data item d ∈ DS which
17

is assigned to Cℓ gets deleted. The structure gets rebuilt in the REFRESH
operation. Thus, the correctness of RSS follows by similar arguments as the
INITIALIZE operation.
[Representant rℓ ∈ Cℓ is not updated] Now consider the (sub-)cases whether
m < logℓ8κ+4κ (n) holds. In case it holds, the representative of Cℓt is still valid
at time t + 1, i.e. rℓ ∈ Cℓt ∩ Cℓt+1 with high probability due to Lemma 4.9 and
Lemma 4.10. On the other hand, if m is large, then rℓ gets deleted from DS
(and hence the whole class Cℓ ) due to Lemma 4.11.
Finally, we show the number of messages the data structure uses in order to
build or rebuild the Rough Rank Sketch.
Theorem 4.13. The operations INITIALIZE and REFRESH use O ( φ1 log1/φ (n))
and O ( φ1 log1/φ (m)) messages in expectation, respectively.
Proof. First, note that the bound on the communication used by INITIALIZE
follows by the same arguments as Lemma 3.3, since INITIALIZE only calls the
CoFaSel protocol. Since there is no early termination rule, i.e. hmin = 1
holds, the protocol uses an amount of O ( φ1 log1/φ (n)) messages in expectation
as claimed above.
Second, for the upper bound of REFRESH, we argue using the law of total
expectation and consider the smallest ℓ such that all ℓ′ > ℓ do not need to
be refreshed, i.e. all representatives of Sℓ′ remain in the data structure. Now
consider the event that m < logℓ8κ (n) holds. It directly follows that the number
of messages to compute the representatives of classes Cℓ′′ with ℓ′′ ≤ ℓ needs
O ( φ1 log1/φ (m) number of messages as claimed. However, if m ≥ logℓ8κ (n) holds,
observe that this event happens with a probability log−c (n), where c directly
depends on the choice of κ. For c > 1 the conditional expected costs yield costs
of only O ( φ1 ), such that the overall costs follow as claimed.

4.3

Implications for Top-k and Approximate k-Select

Here we shortly describe how the data structure can be used to efficiently answer a Top-k or k-Select request. Note that the k does not need to be known
beforehand, each request can be posed with a different parameter.
Both computations start with a REFRESH operation if there were UPDATEs since the last REFRESH. We then obtain an item with rank close to k
with a ROUGH-RANK(k) operation.
For determining the k smallest items, the response from the data structure,
denoted by d, is broadcasted such that all sensor nodes with a larger data item
do not take place in the call of Top-k Protocol with parameter k. If this call was
not successful, a second call of Top-k Protocol is executed on all sensor nodes.
Considering the expected costs conditioned on whether the first or second call
was successful and applying the law of total expectation, the simple bound on
the communication follows:

18

Corollary 4.14. One computation of the Top-k needs k+O (log(m)+log(log(n)))
messages in expectation assuming m UPDATEs are processed since the last Topk query.
Exactly the same approach is used to solve the k-Select problem. We define
the (internal) failure probability δ ′ := log−1 (n) and obtain the following simple
bound by applying the same arguments as for the Top-k Protocol.
Corollary 4.15. One computation of approx. k-Select Problem uses O (Sε,δ +
log(m)+ log2 (log(n))) msg. in expectation assuming m UPDATES are processed
since the last query.

5

Lower Bounds

In this section we consider lower bounds for the problems considered in the past
sections. We show that our main results in the previous sections are asymptotically tight up to additive costs of O (log(log(n))) per time step for a constant
choice of φ, and O (log2 (log(n))), respectively. For scenarios in which the adversary changes a polylogarithmic number of values in each time step, the proposed
bounds are asymptotically tight.
Lemma 5.1 ([4]). Every algorithm needs Ω(log(n)) messages in expectation to
output the maximum in our setting.
We extend this lemma to multiple time steps and to monte carlo algorithms
which solve the problem at each time step with a fixed probability:
Lemma 5.2. Every algorithm that outputs for a given c > 1, a data item d
1
uses
where rank(d) ∈ O (logc (n)) holds and success probability at least 1 − log(n)
Ω(log(n)) messages in expectation in our setting.
Proof. Assume there is an algorithm ALG which achieves the above requirements
with o(log(n)) messages in expectation. We construct an algorithm A which
first applies ALG and then the Top-k Protocol for k := 1, and hmax := log(n)
afterwards.
Observe that A uses O (log(log(n))) messages in expectation if the event
m ≤ logc (n) occurs and log(n) messages, else. The probability that the latter
1
event occurs is upper bounded by log(n)
and thus, A uses o(log(n)) messages in
expectation which contradicts Lemma 5.1.
We further extend the lower bounds to multiple time steps in which an adversary is allowed to change values of at most m nodes between two consecutive
time steps. It is easy to see if the instance always changes the smallest m nodes
between each time steps and chooses random permutations, the following holds:
Theorem 5.3. Every algorithm A that tracks the minimum over T time steps
uses an amount of Ω(log(n) + T log(m)) messages in expectation, if m UPDATES per step are processed in our setting.
19

Proof. For the proof we assume, that T is at most log(n), split T in T1 , T2 , . . .,
each of size log(n) (except for the last one).
Now, construct an instance as follows: Initially define sets of data items
S0 , S1 , . . . , Slog(n) . In each time step the data items for an UPDATE are chosen
from these sets. For each consecutive set St , St+1 holds that the largest data
item in St+1 is smaller than the smallest data item in St . Furthermore, the size
of each St is m, for t ≥ 1 and n for t = 0. The adversary chooses a random
permutation π0 which defines which node initially observes a data item from S0 .
Denote the set of nodes with the m smallest data items given by the random
permutation by N . For each consecutive time step t > 0 the adversary chooses
a random permutation πt of St and chooses the m nodes in N to process these
UPDATES.
Observe that in the first step (t = 0) based on Lemma 5.1 we argue that at
least Ω(log(n)) messages are used to identify the minimum. For each consecutive
time step (t > 0) the adversary chooses the same set of nodes N to process
UPDATES. Based on the construction of St and St−1 no information of St−1
can be exploited by any algorithm to proceed the permutation of St using less
than Ω(log(m)) messages in expectation, concluding the proof.

References
[1] Arackaparambil, C., Brody, J., Chakrabarti, A.: Functional Monitoring
without Monotonicity. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 95–106. Springer,
Berlin (2009)
[2] Cormode, G., Muthukrishnan, S., and Yi, K. Algorithms for distributed
functional monitoring. In Proceedings of the nineteenth annual ACM-SIAM
symposium on Discrete algorithms (SODA ’08). Society for Industrial and
Applied Mathematics, Philadelphia, PA, USA, (2008)
[3] Muthukrishnan, S.: Data Streams: Algorithms and Applications. Now
Publishers Inc, (2005)
[4] Mäcker, A., Malatyali, M., Meyer auf der Heide, F.: Online Top-k-Position
Monitoring of Distributed Data Streams. In: 29th International Parallel
and Distributed Processing Symposium. IEEE, (2015)
[5] Mäcker, A., Malatyali, M., Meyer auf der Heide, F.: On Competitive Algorithms for Approximations of Top-k-Position Monitoring of Distributed
Streams. In: 30th International Parallel and Distributed Processing Symposium. IEEE, (2016)
[6] Zhang, Z., Cheng, R., Papadias, D. and Tung, A.K.H.: Minimizing the
Communication Cost for Continuous Skyline Maintenance. In: Proceedings
of the ACM SIGMOD International Conference on Management of data,
pp. 495–508. ACM, New York (2009)
20

[7] Canetti, Ran, Guy Even, and Oded Goldreich. Lower bounds for sampling
algorithms for estimating the average. Information Processing Letters 53.1
(1995): 17-25.
[8] Zhang, Q.: Communication-Efficient Computation on Distributed Noisy
Datasets. In: Proceedings of the 27th ACM Symposium on Parallelism in
Algorithms and Architectures, pp. 313–322. ACM, (2015)
[9] Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65.1, pp. 206–223. (2013)
[10] Zengfeng, H., Yi, K., Zhang, Q.: Randomized algorithms for tracking distributed count, frequencies, and ranks. Proceedings of the 31st symposium
on Principles of Database Systems, (2012).
[11] Madden, S., Franklin, M., Hellerstein, J., and Hong, W.: The design of an
acquisitional query processor for sensor networks. Proceedings of the 2003
ACM SIGMOD international conference on Management of data, pages
491–502, (2003)
[12] Babcock, B., Olston, C.: Distributed Top-K Monitoring. In: International
Conference on Management of Data, pp.28–39. ACM, (2003)
[13] Cormode, G., Muthukrishnan, S., Ke, Y.: Algorithms for Distributed Functional Monitoring. ACM Transactions on Algorithms 7, 21 (2011)
[14] Marberg, J.: An Optimal Shout-Echo Algorithm for Selection in Distributed Sets. UCLA, (1985)
[15] Rotem, D., Santoro N., Sidney, J.: Shout Echo Selection in Distributed
Files. Networks, vol. 16, pp. 77–86. John Wiley & Sons (1986)
[16] Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D. Space-and timeefficient deterministic algorithms for biased quantiles over data streams. In
Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (pp. 263-272). ACM.
[17] Bemmann, P. and Biermeier, F. and Bürmann, J. and Kemper, A. and
Knollmann, T. and Knorr, S. and Kothe, N. and Mäcker, A. and Malatyali,
M. and Meyer auf der Heide, F. and Riechers, S. and Schaefer, J. and
Sundermeier, J., Monitoring of Domain-Related Problems in Distributed
Data Streams. 24th International Colloquium on Structural Information
and Communication Complexity, to appear (2017)
[18] Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D. Effective computation of biased quantiles over data streams. In Data Engineering, 2005.
ICDE 2005. Proceedings. 21st International Conference on (pp. 20-31).
IEEE.

21

