Michael Langberg

Reza Sayyari, Michael Langberg

We study the secure multiple key-cast problem over noiseless networks under node-based eavesdroppers, where one or more source nodes participate in the generation of distinct secret keys to be shared among designated terminal subsets, while an eavesdropper observing up to $\ell$ nodes, including possibly source nodes, obtains no information about the keys. For the single-source setting, we first consider networks in which every node is $d$-vertex connected from the source. We show that a secure key rate of $d-\ell$ is achievable for all such networks. We further show that this rate is optimal by exhibiting $d$-vertex-connected networks whose secure key-cast capacity is at most $d-\ell$. We next study networks in which only the terminal nodes are $d$-vertex connected from the source, while other network nodes may not satisfy this connectivity condition and may be partially-connected. We show that secure multiple key-cast remains achievable in the presence of such partially-connected nodes, and derive coding schemes whose rate depends on the minimum network vertex-connectivity from the source and certain additional network properties. Finally, we generalize these results, for both $d$-vertex-connected networks and networks containing partially-connected nodes, to the multi-source setting; showing that secure multiple key-cast remains achievable even when the eavesdropper may observe all but one of the source nodes.

Payam Abdisarabshali, Fardis Nadimi, Kasra Borazjani et al.

The rise of foundation models (FMs) has reshaped the landscape of machine learning. As these models continued to grow, leveraging geo-distributed data from wireless devices has become increasingly critical, giving rise to federated foundation models (FFMs). More recently, FMs have evolved into multi-modal multi-task (M3T) FMs (e.g., GPT-4) capable of processing diverse modalities across multiple tasks, which motivates a new underexplored paradigm: M3T FFMs. In this paper, we unveil an unexplored variation of M3T FFMs by proposing hierarchical federated foundation models (HF-FMs), which in turn expose two overlooked heterogeneity dimensions to fog/edge networks that have a direct impact on these emerging models: (i) heterogeneity in collected modalities and (ii) heterogeneity in executed tasks across fog/edge nodes. HF-FMs strategically align the modular structure of M3T FMs, comprising modality encoders, prompts, mixture-of-experts (MoEs), adapters, and task heads, with the hierarchical nature of fog/edge infrastructures. Moreover, HF-FMs enable the optional usage of device-to-device (D2D) communications, enabling horizontal module relaying and localized cooperative training among nodes when feasible. Through delving into the architectural design of HF-FMs, we highlight their unique capabilities along with a series of tailored future research directions. Finally, to demonstrate their potential, we prototype HF-FMs in a wireless network setting and release the open-source code for the development of HF-FMs with the goal of fostering exploration in this untapped field (GitHub: https://github.com/payamsiabd/M3T-FFM).

Prachi Mishra, Sidharth Jaggi, Navin Kashyap et al.

We investigate weakly constrained codes, in which specific patterns occur with prescribed frequencies rather than being strictly forbidden as in conventional constrained coding. We propose a capacity-achieving construction of a weakly constrained codebook based on Eulerian cycles. We then obtain, via expurgation, weakly constrained codes with linear minimum distance and positive rate, and analyze the rates achievable. Finally, we propose a practical concatenated code construction that supports polynomial-time encoding and decoding.

Payam Abdisarabshali, Kwang Taik Kim, Michael Langberg et al.

Existing studies on federated learning (FL) are mostly focused on system orchestration for static snapshots of the network and making static control decisions (e.g., spectrum allocation). However, real-world wireless networks are susceptible to temporal variations of wireless channel capacity and users' datasets. In this paper, we incorporate multi-granular system dynamics (MSDs) into FL, including (M1) dynamic wireless channel capacity, captured by a set of discrete-time events, called $\mathscr{D}$-Events, and (M2) dynamic datasets of users. The latter is characterized by (M2-a) modeling the dynamics of user's dataset size via an ordinary differential equation and (M2-b) introducing dynamic model drift}, formulated via a partial differential inequality} drawing concrete analytical connections between the dynamics of users' datasets and FL accuracy. We then conduct FL orchestration under MSDs by introducing dynamic cooperative FL with dedicated MAC schedulers (DCLM), exploiting the unique features of open radio access network (O-RAN). DCLM proposes (i) a hierarchical device-to-device (D2D)-assisted model training, (ii) dynamic control decisions through dedicated O-RAN MAC schedulers, and (iii) asymmetric user selection. We provide extensive theoretical analysis to study the convergence of DCLM. We then optimize the degrees of freedom (e.g., user selection and spectrum allocation) in DCLM through a highly non-convex optimization problem. We develop a systematic approach to obtain the solution for this problem, opening the door to solving a broad variety of network-aware FL optimization problems. We show the efficiency of DCLM via numerical simulations and provide a series of future directions.

Allan Salihovic, Payam Abdisarabshali, Michael Langberg et al.

We provide our perspective on X-Learning (XL), a novel distributed learning architecture that generalizes and extends the concept of decentralization. Our goal is to present a vision for XL, introducing its unexplored design considerations and degrees of freedom. To this end, we shed light on the intuitive yet non-trivial connections between XL, graph theory, and Markov chains. We also present a series of open research directions to stimulate further research.

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg et al.

We consider the problem of communicating a message $m$ in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to $pn$ bits, out of $n$ transmitted bits $(x_1,\ldots,x_n)$. The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit $x_i$ depends on his observations $(x_1,\ldots,x_i)$ was recently characterized to be $1-2p$. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit $x_i$ depends only on $(x_1,\ldots,x_{i-1})$ (and is independent of the "current bit" $x_i$) then the capacity increases to $1-p$ when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword is a deterministic function of the message $m$) then no rate asymptotically larger than $1-2p$ is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of $1-p$ against a one-bit-delayed Calvin.

Wentao Huang, Michael Langberg, Joerg Kliewer et al.

A secret sharing scheme is a method to store information securely and reliably. Particularly, in a threshold secret sharing scheme, a secret is encoded into $n$ shares, such that any set of at least $t_1$ shares suffice to decode the secret, and any set of at most $t_2 < t_1$ shares reveal no information about the secret. Assuming that each party holds a share and a user wishes to decode the secret by receiving information from a set of parties; the question we study is how to minimize the amount of communication between the user and the parties. We show that the necessary amount of communication, termed "decoding bandwidth", decreases as the number of parties that participate in decoding increases. We prove a tight lower bound on the decoding bandwidth, and construct secret sharing schemes achieving the bound. Particularly, we design a scheme that achieves the optimal decoding bandwidth when $d$ parties participate in decoding, universally for all $t_1 \le d \le n$. The scheme is based on Shamir's secret sharing scheme and preserves its simplicity and efficiency. In addition, we consider secure distributed storage where the proposed communication efficient secret sharing schemes further improve disk access complexity during decoding.

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg et al.

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword $(x_1,...,x_n)$ bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits $x_i$ one at a time, and can change up to a $p$-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit $x_i$ the jammer's decision on whether to corrupt it or not must depend only on $x_j$ for $j \leq i$. This is in contrast to the "classical" adversarial jamming situations in which the jammer has no knowledge of $(x_1,...,x_n)$, or knows $(x_1,...,x_n)$ completely. In this work, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.