Less Communication

A set of $k$ servers are receiving requests and they are required to report to a coordinator the numbers of requests they process. An event is trigerrd by the coordinator if the culmulative requests received by the serves reaches a threshold $\tau$. The goal is to minimized the communicaiton between the coordinator and the servers.

A naive approach asks the servers to send a notificiation to the coordinator each time they process a request, resulting in $O(\tau)$ bits communication in total.

An alternative approach achieves $O(h \log \tau)$ words communication cost. Instead of response to the coordinator every a new request comes, the server reports only after some requests reaches. However, we don't want the coordinator to miss the $\tau$ threshold, i.e., it must triger the event when exactly $\tau$ requests come in total.

Here is the scheme.

1. If $\tau \le 5 \cdot h$, the server report each time a request comes.
2. The coordinator sends the threshold $\lfloor \frac{\tau}{ 2h} \rfloor$ to each server. This requires $h$ words.
3. Each server sends a report to the coordinator every $\lfloor \frac{\tau}{ 2h} \rfloor$ requests comes.
4. When the coordinator learns that, the servers has processed $\lfloor \tau / 2 \rfloor$ requests (at most $2h$ words communication needed), it collects how many requests are proceed in each servers which are not reported to it (at most $2h$ words communication needed). The number of requests comes is at most$$\lfloor \tau / 2 \rfloor + (h - 1) (\lfloor \tau / 2h \rfloor - 1) < \tau /2 + \tau / 2 = \tau$$
5. The number of requests remains to reach the $\tau$ threshold is at most $\tau' \doteq \lceil \tau / 2 \rceil$. We set $\tau'$ as the new threshold and go to step 1.
6. The overall communication cost is given by$$T(\tau) = T(\lceil \tau / 2 \rceil) + 5 \cdot h$$for some constant $k$.
7. There are at most $2 \log \tau$ recursions. Each recursion requires $k$ words communication, resulting in a total communication cost $O(h \log \tau)$ words.