## 2 Related Work  
Fundamental limits on computing a class of functions called _divisible_ functions \(f(\cdot)\) are studied in [1]. The divisible functions are a class of functions that can be computed in divide-and-conquer manner without affecting the final result. Suppose there are a set of \(n\) data samples. Divide the set into two arbitrary groups of \(k\) and \(n-k\) samples. Let us denote the data of the first and second group by \(x_{1},x_{2},\ldots,x_{k}\) and \(x_{k+1},\ldots,x_{n}\) respectively. If \(f(\cdot)\) is divisible, \(f(f(x_{1},\ldots,x_{k}),f(x_{k+1},\ldots,x_{n}))=f(x_{1},x_{2},\ldots,x_{n})\) holds for any \(n\) and \(k\). The divisible functions enable efficient in-network aggregation. Examples of divisible functions are sum, max and min. Moreover [1] showed that when computing max or min functions, one can achieve particularly low overhead in communications which scales as at most \(O(\text{log}(n))\). This suggests that there is much room for performance improvement in retrieving the extreme data. A number of data gathering problems aiming at achieving low latency have been studied. The trade-off between energy and data gathering latency is investigated in [6]. The authors study an aggregation strategy for minimizing energy dissipation exploiting the fact that longer transmission time of a packet can save energy expenditure, _i.e._, a link-level trade-off studied in [7]. A series of works [8, 9, 10] have focused on scheduling of data aggregation in order to minimize latency. In [10] a scheduling algorithm of the links in aggregation tree using maximal independent set to achieve a latency bound which scales additively in network radius and maximum degree. The efficiency of in-network aggregation is characterized by the following trade-off between traffic reduction and latency. A node may wait for sufficient amount of data to be aggregated before forwarding the aggregated information to the next-hop node. The longer a node waits for aggregation, the more the traffic is decreased. The decrease in traffic reduces contention for channel access, which improves the efficiency of in-network aggregation. On the other hand, such waiting time incurs extra latency in the data gathering process. Thus the question is how long nodes should wait before transmitting the aggregated information when there is a deadline constraint. The work of [11] formulates such decision making as semi-Markov Decision Process. They propose an approximation algorithm for finding the optimal waiting time for aggregation in order to maximize the'reward'. The reward is defined as a function of the number of samples collected at the sink before deadline. Also [12] proposed a framework based on dynamic programming for maximizing the number of packets reaching the sink under energy and deadline constraints. The work [13] studies a similar problem of maximizing the amount of collected information using dynamic programming. They consider a contention-based MAC using CSMA/CA, and find the optimal waiting time for aggregation and the associated MAC parameters. Unlike these works we do _not_ consider optimizing such waiting times. In the proposed scheme, a node attempts transmission if there is any data to send, and does not wait for further aggregation of data. Instead we focus on distributed, priority-based channel access and techniques specific to retrieving the maximum value. However it is clear that the proposed scheme can be easily extended to schemes such that the nodes wait for the aggregation of data. Such extension should address the problem of optimizing waiting time under the proposed medium access and data combining scheme, which is a possible direction for future study. We also mention that our scheme is fully distributed and has very low overhead that is independent of the network size. A number of recent works discussed distributed medium access based on priority.