In order to achieve the dual goals of privacy and learning across distributed data, Federated Learning (FL) systems rely on frequent exchanges of large files (model updates) between a set of clients and the server. As such FL systems are exposed to, or indeed the cause of, congestion across a wide set of network resources. Lossy compression can be used to reduce the size of exchanged files and associated delays, at the cost of adding noise to model updates. By judiciously adapting clients’ compression to varying network congestion, an FL application can reduce wall clock training time. To that end, we propose a Network Adaptive Compression (NAC-FL) policy, which dynamically varies the client’s lossy compression choices to network congestion variations. We prove, under appropriate assumptions, that NAC-FL is asymptotically optimal in terms of directly minimizing the expected wall clock training time. Further, we show via simulation that NAC-FL achieves robust performance improvements with higher gains in settings with positively correlated delays across time.

Underlying blockchain's scalability and performance is a Peer-to-Peer (P2P) overlay network and protocols for relaying blocks and transactions among participating nodes. In this work, we model and perform a systematic analysis of blockchain communication protocols. We begin by introducing the performance metric of interest for blockchains, the sequence of ordered-completion-times, which captures the progress distributed nodes are making in jointly constructing a consistent blockchain. We then study the characteristics of block relaying protocols. In particular, we show that when nodes cannot perform cut-through relaying, there is no optimal causal block relaying protocol if block relaying times are deterministic. We propose a simple age-based block relaying protocol that is provably near-optimal in terms of minimizing ordered-completion-times when the P2P overlay network is a tree. This analysis is relevant to blockchain relay networks such as Bitcoin-Fibre, Bloxroute etc., where the core part of the overlay is a tree. Finally, using the insights derived for tree overlays, we explore the interplay between transaction and block relaying and prioritization (age, size, FCFS based) on both tree and fully connected overlays via simulation. We observe that policies that relay blocks and incorporate transactions into blocks based on 'age' outperform other natural policies. We also explore a fundamental tradeoff between mining and computational efficiencies and performance (in terms of ordered completion times).

A single server with variable speed and a finite buffer is considered under a maximum packet drop probability constraint. The cost of processing by the server is a convex function of the speed of the server. If a packet arrives when the buffer is full, it is dropped instantaneously. Given the finite server buffer, the objective is to find the optimal dynamic server speed to minimize the overall cost subject to the maximum packet drop probability constraint. Finding the exact optimal solution is known to be hard, and hence algorithms with provable approximation bounds are considered. We show that if the buffer size is large enough, the proposed algorithm achieves the optimal performance. For arbitrary buffer sizes, constant approximation guarantees are derived for a large class of packet arrival distributions such as Bernoulli, Exponential, Poisson etc.