We consider the problem of federated learning in a one-shot setting in which there are$m$machines, each observing$n$sample functions from an unknown distribution on non-convex loss functions. Let$F:[-1,1]^{d}\to {\mathbb {R}} $be the expected loss function with respect to this unknown distribution. The goal is to find an estimate of the minimizer of$F$. Based on its observations, each machine generates a signal of bounded length$B$and sends it to a server. The server collects signals of all machines and outputs an estimate of the minimizer of$F$. We show that the expected loss of any algorithm is lower bounded by$\max \big (1/(\sqrt {n}(mB)^{1/d}), 1/\sqrt {mn}\big)$, up to a logarithmic factor. We then prove that this lower bound is order optimal in$m$and$n$by presenting a distributed learning algorithm, called Multi-Resolution Estimator for Non-Convex loss function (MRE-NC), whose expected loss matches the lower bound for large$mn$up to polylogarithmic factors.

We consider distributed statistical optimization in one-shot setting, where there are $m$ machines each observing $n$ i.i.d. samples. Based on its observed samples, each machine sends a $B$-bit-long message to a server. The server then collects messages from all machines, and estimates a parameter that minimizes an expected convex loss function. We investigate the impact of communication constraint, $B$, on the expected error and derive a tight lower bound on the error achievable by any algorithm. We then propose an estimator, which we call Multi-Resolution Estimator (MRE), whose expected error (when $B\ge d\log mn$ where $d$ is the dimension of parameter) meets the aforementioned lower bound up to a poly-logarithmic factor in $mn$. The expected error of MRE, unlike existing algorithms, tends to zero as the number of machines ($m$) goes to infinity, even when the number of samples per machine ($n$) remains upper bounded by a constant. We also address the problem of learning under tiny communication budget, and present lower and upper error bounds for the case that the budget $B$ is a constant.

We consider distributed statistical optimization in one-shot setting, where there are $m$ machines each observing $n$ i.i.d samples. Based on its observed samples, each machine then sends an $O(\log(mn))$-length message to a server, at which a parameter minimizing an expected loss is to be estimated. We propose an algorithm called Multi-Resolution Estimator (MRE) whose expected error is no larger than $\tilde{O}( m^{-1/\max(d,2)} n^{-1/2})$, where $d$ is the dimension of the parameter space. This error bound meets existing lower bounds up to poly-logarithmic factors, and is thereby order optimal. The expected error of MRE, unlike existing algorithms, tends to zero as the number of machines ($m$) goes to infinity, even when the number of samples per machine ($n$) remains upper bounded by a constant. This property of the MRE algorithm makes it applicable in new machine learning paradigms where $m$ is much larger than $n$.

Considering the collection of all networks with independent set interference model, Shah, Tse, and Tsitsiklis showed that there exist scheduling algorithms with polynomial complexity and delay, only if the maximum independent set problem can be solved in polynomial time (equivalently, P=NP). In this paper, we extend this result to arbitrary collections of networks and present a clear-cut criterion for the existence of polynomial complexity and delay scheduling algorithms relative to a given collection of networks with arbitrary interference models, not confined to independent set interference or SINR models, and not necessarily encompassing all network topologies. This amounts to the equivalence of polynomial scheduling and effective approximation of maximum weighted actions.

In the binary majority voting problem, each node initially chooses between two alternative choices. The goal is to design a distributed algorithm that informs nodes which choice is in majority. In this study, the authors formulate this problem as a hypothesis testing problem and propose fixed‐size and sequential solutions using classical and Bayesian approaches. In the sequential version, the proposed mechanism enables nodes to test which choice is in majority, successively in time. Hence, termination of the algorithm is embedded within it, contrary to the existing approaches which require a monitoring algorithm to indicate the termination. This property makes the algorithm more efficient in terms of message complexity. Furthermore, the authors show that the proposed solution is resilient to Byzantine attacks if network connectivity is F + 1 in the presence of F adversarial nodes. Thus, the proposed algorithm is more robust compared with the previous works which are vulnerable to the existence of adversarial nodes.

In distributed function computation, each node has an initial value and the goal is to compute a function of these values in a distributed manner. In this paper, we propose a novel token-based approach to compute a wide class of target functions to which we refer as “token-based function computation with memory” (TCM) algorithm. In this approach, node values are attached to tokens and travel across the network. Each pair of travelling tokens would coalesce when they meet, forming a token with a new value as a function of the original token values. In contrast to the coalescing random walk (CRW) algorithm, where token movement is governed by random walk, meeting of tokens in our scheme is accelerated by adopting a novel chasing mechanism. We proved that, compared to the CRW algorithm, the TCM algorithm results in a reduction of time complexity by a factor of at least √(n/log(n) in Erdos-Renyi and complete graphs, and by a factor of log (n)/log(log(n)) in torus networks. Simulation results show that there is at least a constant factor improvement in the message complexity of TCM algorithm in all considered topologies. Robustness of the CRW and TCM algorithms in the presence of node failure is analyzed. We show that their robustness can be improved by running multiple instances of the algorithms in parallel.

Averaging consensus on the values of nodes in a network is a principal problem in distributed computation. In the presence of erasure channels, conventional averaging consensus algorithms may not converge to the average value if packets are erased in arbitrary order. In this paper, we propose a “Pseudo-Synchronous Averaging Consensus” (PSAC) algorithm to guarantee averaging consensus over erasure channels by employing tagged packets. We show that the PSAC algorithm has a simple structure and it can work with just two tags “0” and “1”. In asynchronous networks, the PSAC algorithm is a synchronizer in the sense that it keeps the updates of various nodes in step with each other. By exploiting the broadcast nature of wireless links in complete graphs, the PSAC algorithm obtains the exact average value with minimum number of transmissions, in the asynchronous setting.

We study the asymptotic behavior of the capacity of erasure networks under a restricted class of network coding schemes, called spatial network coding. In spatial network coding, nodes are permitted to only combine data units received from distinct incoming links; multiple data units arriving on the same link may not be coded together. Elsewhere, it has been shown that the network capacity under spatial network coding is the statistical mean of the minimum cut value. In this paper, we come up with a new concept in the random graph theory referred to as typical min-cut family, which parallels the information theoretic notion of typical sequences, and use it to develop an analytical tool for the comparison of the capacity under spatial network coding and the capacity under unrestricted coding. Applying this tool to point-to-point erasure networks with a regular multi-layer topology, we show that, as the number of nodes per layer increases, the capacity under spatial network coding asymptotically converges to the capacity under unrestricted coding, provided that the number of layers separating the source and the destination does not increase faster than exponentially, with respect to the number of nodes per layer. Numerical study, showing fast convergence, suggests that spatial diversity may be exploited through network coding to provide an effective substitute for time diversity, where the latter cannot be exploited.

A new approach to joint scheduling, flow control and routing in wireless networks, based on formulation as a convex optimization problem is presented. This approach is novel in that it integrates optimal scheduling and flow control with a modified version of minimum delay routing, resulting in significant performance advantage over alternative approaches. We come up with a distributed algorithm for implementation of the proposed scheme and show, by analysis and simulation, that the algorithm achieves fairness and/or priorities among users in accordance with pre-assigned user parameters. In sharp contrast to alternative algorithms that perform scheduling and packet routing based on per-session queue differential between adjacent nodes, our algorithm uses a complete multi-hop view of network conditions for packet routing and retains the desirable properties of minimum delay routing. As the result, it achieves queue sizes and end-to-end delays that are several times smaller, without compromising the throughput.

A joint routing and scheduling algorithm for multi- hop wireless networks, based on a unified convex optimization framework, is proposed. Our approach is novel in that it integrates optimal scheduling with a modified version of distributed minimum delay routing. Accordingly, the algorithm performs packet routing based on a complete multi-hop view of the network and its traffic conditions. This stands in sharp contrast to joint routing and scheduling algorithms, such as the Tassiulas algorithm, that rely on per-session queue differential between adjacent nodes for channel scheduling and packet routing. Simulation results illustrate that the proposed algorithm performs much better than Tassiulas, in terms of packet delay and jitter, packet loss and misordering, and energy consumption. Moreover, in terms of capacity region, simulation results do not reflect any noticeable difference between the two algorithms.

No packets will be dropped inside a packet network, even when congestion builds up, if congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity-stopping them from forwarding more packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part of the network goes to zero (i.e., no packets are transmitted). In this paper, we describe a simple, lossless method of preventing deadlocks and livelocks in backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt packet sequence, and does not require any changes to packet headers. It represents a new networking paradigm in which internal network losses are avoided (thereby simplifying the design of other network protocols) and internal network delays are bounded.

When congestion builds up in a packet network, two general approaches are possible to cope with the shortage of buffer space. One approach is to drop incoming packets for the buffer that is not available and to rely on the end-to-end protocols for the recovery of lost packets. The alternative approach is to insist that no packets should be dropped inside a packet network, even when congestion builds up. One way to accomplish this goal is to have the congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity and in effect stopping them from forwarding packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part of the network goes to zero (i.e., no packets are transmitted). In this paper, we describe a simple, lossless method of preventing deadlocks and livelocks in backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt the packet sequence, and does not require any changes to packet headers. In addition to presenting the new congestion control protocol in a general context, we describe an important application of the technique to Gigabit Ethernet (IEEE 802.3z).

We study congestion control for one-to-many multicast applications in the Internet and establish a three-way relationship between the choice of regulation parameter (i.e., rate or window size), the requirement to estimate receiver round trip times, and the type of fairness that may be accomplished. In particular, we show that in order to provide TCP-compatible fairness in rate-based regulation, receiver round trip times must be known. However, such a requirement does not exist in window-based regulation. We further show that measurement of receiver round-trip times in multicast communication, is fundamentally different and more complex than unicast communication, in order to avoid implosion of acknowledgments at the source. A major part of the paper deals with extending window-based regulation to multicast communications. We show that window-based regulation using a common window-size for the whole session leads to unnecessary restrictions on the throughput. To alleviate this problem, we propose a multicast window scheme using a distinct window size for each receiver, and enforcing it as the limit on the number of outstanding packets to that receiver. The complexity of window-based regulation can be defused by a receiver-driven implementation and by consolidation of receiver feedback in successive stages, e.g., using a hierarchical architecture. This hierarchical approach is also useful for scalable consolidation of receiver feedback in the case of rate-based regulation, and for distributed estimation of receiver round trip times, when such estimation is necessary.

We formulate end-to-end congestion control as a global optimization problem. Based on this formulation, a class of minimum cost flow control (MCFC) algorithms for adjusting session rates or window sizes is proposed. Significantly, we show that these algorithms can be implemented at the transport layer of an IP network and can provide certain fairness properties and user priority options without requiring non-FIFO switches. Two algorithm versions are discussed. A coarse version is geared towards implementation in the current Internet, relying on the end-to-end packet loss observations as an indication of congestion. A more complete version anticipates an Internet where sessions can solicit explicit congestion information through a concise probing mechanism. We show that TCP congestion control, after some modification, may be treated as a special case of the MCFC algorithms.

A self-clocked fair queueing (SCFQ) scheme has been proposed by Golestani (see Proc. IEEE INFOCOM, p. 636-636, 1994) as an easily implementable version of fair queueing. In this paper, the worst case network delay performance of a class of fair queueing algorithms, including the SCFQ scheme, is studied. We build upon and generalize the methodology developed by Parekh and Gallager (see ACM/IEEE Trans. Networking, vol.1, no.3, p.344-357, 1993, and vol.2, no.2, p.137-150, 1994) to study this class of algorithms based on the leaky-bucket characterization of traffic. Under modest resource allocation conditions, the end-to-end session delays and backlogs corresponding to this class of algorithms are shown to be bounded. For the SCFQ scheme, these bounds are larger, but practically as good as the corresponding bounds for the PGPS scheme. It is shown that the SCFQ scheme can provide adequate performance guarantees for the delay-sensitive traffic in ATM.>

An efficient fair queueing scheme which is feasible for broadband implementation is proposed and its performance is analyzed. The author defines fairness in a self-contained manner, eliminating the need for the hypothetical fluid-flow reference system used in the present state of art and thereby removing the associated computational complexity. The scheme is based on the adoption of an internally generated virtual time as the index of work progress, hence the name self-clocked fair queueing. The author proves that the scheme possesses the desired fairness property and is nearly optimal, in the sense that the maximum permissible disparity among the normalized services offered to the backlogged sessions is never more than two times the corresponding figure in any packet-based queueing system.>

A novel strategy for the transmission and multiplexing of delay-sensitive traffic, e.g., voice and video, in packet networks is described. The strategy provides bounded end-to-end delay to all delay-sensitive traffic guarantees loss-free transmission to any traffic with such a requirement. To achieve statistical multiplexing gain, loss performance is provided to the rest of delay-sensitive traffic on an as-needed basis, with possible distinction among different classes. Bounded end-to-end delay is obtained by performing statistical multiplexing at the switching nodes on a duration-limited basis. Loss-free transmission is achieved by means of an underlying service discipline called stop-and-go queuing. The performance of the strategy for some special cases is analyzed, and analytical expressions for the loss probability are derived.>

A congestion management strategy for integrated services packet networks that is robust with regard to transmission speed and network size is proposed. The strategy supports several classes of services with zero loss and different delay bounds as well as services without stringent loss and delay guarantees. Loss-free and bounded-delay transmission is accomplished by means of an admission policy which ensure smoothness of the traffic at the network edge, and by a service discipline called stop-and-go queuing, which maintains the traffic smoothness throughout the network. Both the admission policy and the stop-and-go queuing are based on a time framing concept described elsewhere by the author (IEEE Trans. Commun., vol.39, Dec.1991). This concept is further developed to incorporate several frame sizes into the strategy, thereby providing flexibility in meeting throughput and delay requirements of different applications. Stop-and-go queueing is realizable with minor modification to a first-in first-out (FIFO) queueing structure.>

The process of packet clustering in a network with well-regulated input traffic is studied and a strategy for congestion-free communication in packet networks is proposed. The strategy provides guaranteed services per connection with no packet loss and an end-to-end delay which is a constant plus a small bounded jitter term. It is composed of an admission policy imposed per connection at the source node, and a particular queuing scheme practiced at the switching nodes, which is called stop-and-go queuing. The admission policy requires the packet stream of each connection to possess a certain smoothness property upon arrival at the network. This is equivalent to a peak bandwidth allocation per connection. The queuing scheme eliminates the process of packet clustering and thereby preserves the smoothness property as packets travel inside the network. Implementation is simple.>

The process of packet clustering in a network with well-regulated input traffic is studied. Based on this study, a strategy for congestion-free communication in packet networks is proposed. The strategy provides guaranteed services per connection with no packet loss and an end-to-end delay which is a constant plus a small bounded jitter term. Therefore, it provides an attractive solution for the transmission of real-time traffic in packet networks. The strategy is composed of an admission policy imposed per connection at the source node and a particular queuing scheme, called stop-and-go queuing, practiced at the switching nodes. The admission policy requires the packet stream of each connection to possess a certain smoothness property upon arrival to the network, while the queuing scheme eliminates the process of packet clustering and thereby preserves the smoothness property as packets travel inside the network. Implementation of the stop-and-go queuing is simple, with little processing overhead and minor hardware modifications to the conventional FIFO (first in, first out) queuing structure.>

A framework for congestion management in integrated services packet networks based on a particular service discipline, called stop-and-go queueing, is proposed. In this framework, loss-free and bounded-delay transmission is provided to the class of traffic with stringent delay and loss requirements, e.g., real-time traffic, while the bursty traffic without such requirements is treated on a different basis to achieve high transmission efficiency. Loss-free and bounded-delay transmission is accomplished by means of an admission policy which ensures smoothness of the traffic at the network edge, and the stop-and-go queueing which maintains the traffic smoothness throughout the network. Both the admission policy and the stop-and-go queueing are based on a time framing concept, addressed in a previous paper. This concept is further developed here to incorporate several frame sizes into the strategy, thereby providing the necessary flexibility in accommodating throughput and end-to-end delay requirements of different connections on an as-needed basis.