Search

We consider a slotted communication system consisting of a source, a cache, a user and a timestomping adversary. The time horizon consists of total $T$ time slots, such that the source transmits update packets to the user directly over $T_{1}$ time slots and to the cache over $T_{2}$ time slots. We consider $T_{1}\ll T_{2}$, $T_{1}+T_{2} < T$, such that the source transmits to the user once between two consecutive cache updates. Update packets are marked with timestamps corresponding to their generation times at the source. All nodes have a buffer size of one and store the packet with the latest timestamp to minimize their age of information. In this setting, we consider the presence of an oblivious adversary that fully controls the communication link between the cache and the user. The adversary manipulates the timestamps of outgoing packets from the cache to the user, with the goal of bringing staleness at the user node. At each time slot, the adversary can choose to either forward the cached packet to the user, after changing its timestamp to current time $t$, thereby rebranding an old packet as a fresh packet and misleading the user into accepting it, or stay idle. The user compares the timestamps of every received packet with the latest packet in its possession to keep the fresher one and discard the staler packet. If the user receives update packets from both cache and source in a time slot, then the packet from source prevails. The goal of the source is to design an algorithm to minimize the average age at the user, and the goal of the adversary is to increase the average age at the user. We formulate this problem in an online learning setting and provide a fundamental lower bound on the competitive ratio for this problem. We further propose a deterministic algorithm with a provable guarantee on its competitive ratio.

We consider a gossip network consisting of a source generating updates and $n$ nodes connected in a two-dimensional square grid. The source keeps updates of a process, that might be generated or observed, and shares them with the grid network. The nodes in the grid network communicate with their neighbors and disseminate these version updates using a push-style gossip strategy. We use the version age metric to quantify the timeliness of information at the nodes. We find an upper bound for the average version age for a set of nodes in a general network. Using this, we show that the average version age at a node scales as $O(n^{\frac{1}{3}})$ in a grid network. Prior to our work, it has been known that when $n$ nodes are connected on a ring the version age scales as $O(n^{\frac{1}{2}})$, and when they are connected on a fully-connected graph the version age scales as $O(\log n)$. Ours is the first work to show an age scaling result for a connectivity structure other than the ring and fully-connected networks that represent two extremes of network connectivity. Our work shows that higher connectivity on a grid compared to a ring lowers the age experience of each node from $O(n^{\frac{1}{2}})$ to $O(n^{\frac{1}{3}})$.

In federated submodel learning (FSL), a machine learning model is divided into multiple submodels based on different types of data used for training. Each user involved in the training process only downloads and updates the submodel relevant to the user's local data, which significantly reduces the communication cost compared to classical federated learning (FL). However, the index of the submodel updated by the user and the values of the updates reveal information about the user's private data. In order to guarantee information-theoretic privacy in FSL, the model is stored at multiple non-colluding databases, and the user sends queries and updates to each database in such a way that no information is revealed on the updating submodel index or the values of the updates. In this work, we consider the practical scenario where the multiple non-colluding databases are allowed to have arbitrary storage constraints. The goal of this work is to develop read-write schemes and storage mechanisms for FSL that efficiently utilize the available storage in each database to store the submodel parameters in such a way that the total communication cost is minimized while guaranteeing information-theoretic privacy of the updating submodel index and the values of the updates. As the main result, we consider both heterogeneous and homogeneous storage constrained databases, and propose private read-write and storage schemes for the two cases., arXiv admin note: text overlap with arXiv:2302.03670

We consider an asynchronous hierarchical federated learning (AHFL) setting with a client-edge-cloud framework. The clients exchange the trained parameters with their corresponding edge servers, which update the locally aggregated model. This model is then transmitted to all the clients in the local cluster. The edge servers communicate to the central cloud server for global model aggregation. The goal of each client is to converge to the global model, while maintaining timeliness of the clients, i.e., having optimum training iteration time. We investigate the convergence criteria for such a system with dense clusters. Our analysis shows that for a system of $n$ clients with fixed average timeliness, the convergence in finite time is probabilistically guaranteed, if the nodes are divided into $O(1)$ number of clusters, that is, if the system is built as a sparse set of edge servers with dense client bases each.

We consider a time slotted communication network with a base station (BS) and a user. At each time slot a fresh update packet arrives at the BS with probability $p>0$. When the BS transmits an update packet for the first time, it goes through with a success probability of $q_1$. In all subsequent re-transmissions, the packet goes through with a success probability of $q_2$ where $q_2>q_1$, due to the accumulation of observations at the receiver used to decode the packet. When the packet goes through the first time, the age of the user drops to 1, while when the packet goes through in subsequent transmissions, the age of the user drops to the age of the packet since its generation. Thus, when the BS is in the process of re-transmitting an old packet, if it receives a new packet, it has to decide whether to re-transmit the old packet with higher probability of successful transmission but resulting in higher age, or to transmit the new packet which will result in a lower age upon successful reception but this will happen with lower probability. In this paper, we provide an optimal algorithm to solve this problem.

We consider a special case of $X$-secure $T$-private information retrieval (XSTPIR), where the security requirement is \emph{asymmetric} due to possible missing communication links between the $N$ databases considered in the system. We define the problem with a communication matrix that indicates all possible communications among the databases, and propose a database grouping mechanism that collects subsets of databases in an optimal manner, followed by a group-based PIR scheme to perform asymmetric XSTPIR with the goal of maximizing the communication rate (minimizing the download cost). We provide an upper bound on the general achievable rate of asymmetric XSTPIR, and show that the proposed scheme achieves this upper bound in some cases. The proposed approach outperforms classical XSTPIR under certain conditions, and the results of this work show that unlike in the symmetric case, some databases with certain properties can be dropped to achieve higher rates, concluding that more databases is not always better.

We consider a network of $n$ user nodes that receives updates from a source and employs an age-based gossip protocol for faster dissemination of version updates to all nodes. When a node forwards its packet to another node, the packet information gets mutated with probability $p$ during transmission, creating misinformation. The receiver node does not know whether an incoming packet information is different from the packet information originally at the sender node. We assume that truth prevails over misinformation, and therefore, when a receiver encounters both accurate information and misinformation corresponding to the same version, the accurate information gets chosen for storage at the node. We study the expected fraction of nodes with correct information in the network and version age at the nodes in this setting using stochastic hybrid systems (SHS) modelling and study their properties. We observe that very high or very low gossiping rates help curb misinformation, and misinformation spread is higher with moderate gossiping rates. We support our theoretical findings with simulation results which shed further light on the behavior of above quantities.

Private information retrieval (PIR) is a privacy setting that allows a user to download a required message from a set of messages stored in a system of databases without revealing the index of the required message to the databases. PIR was introduced under computational privacy guarantees, and is recently re-formulated to provide information-theoretic guarantees, resulting in \emph{information theoretic privacy}. Subsequently, many important variants of the basic PIR problem have been studied focusing on fundamental performance limits as well as achievable schemes. More recently, a variety of conceptual extensions of PIR have been introduced, such as, private set intersection (PSI), private set union (PSU), and private read-update-write (PRUW). Some of these extensions are mainly intended to solve the privacy issues that arise in distributed learning applications due to the extensive dependency of machine learning on users' private data. In this article, we first provide an introduction to basic PIR with examples, followed by a brief description of its immediate variants. We then provide a detailed discussion on the conceptual extensions of PIR, along with potential research directions.

In federated learning (FL) with top $r$ sparsification, millions of users collectively train a machine learning (ML) model locally, using their personal data by only communicating the most significant $r$ fraction of updates to reduce the communication cost. It has been shown that the values as well as the indices of these selected (sparse) updates leak information about the users' personal data. In this work, we investigate different methods to carry out user-database communications in FL with top $r$ sparsification efficiently, while guaranteeing information theoretic privacy of users' personal data. These methods incur considerable storage cost. As a solution, we present two schemes with different properties that use MDS coded storage along with a model segmentation mechanism to reduce the storage cost at the expense of a controllable amount of information leakage, to perform private FL with top $r$ sparsification., Comment: arXiv admin note: text overlap with arXiv:2212.09704

We consider a semantics-aware communication system, where timeliness is the semantic measure, with a source which maintains the most current version of a file, and a network of $n$ user nodes with the goal to acquire the latest version of the file. The source gets updated with newer file versions as a point process, and forwards them to the user nodes, which further forward them to their neighbors using a memoryless gossip protocol. We study the average version age of the network in the presence of $\tilde{n}$ jammers that disrupt inter-node communications, for the connectivity-constrained ring topology and the connectivity-rich fully connected topology. For the ring topology, we construct an alternate system model of mini-rings and prove that the version age of the original model can be sandwiched between constant multiples of the version age of the alternate model. We show in a ring network that when the number of jammers scales as a fractional power of the network size, i.e., $\tilde n= cn^\alpha$, the version age scales as $\sqrt{n}$ when $\alpha < \frac{1}{2}$, and as $n^{\alpha}$ when $\alpha \geq \frac{1}{2}$. As version age of a ring network without any jammers scales as $\sqrt{n}$, our result implies that version age with gossiping is robust against upto $\sqrt{n}$ jammers in a ring network. We then study the connectivity-rich fully connected topology, where we derive a greedy approach to place $\tilde{n}$ jammers to maximize age of the resultant network, which uses jammers to isolate as many nodes as possible, thereby consolidating all links into a single mini-fully connected network. We show in this network that version age scales as $\log{n}$ when $\tilde{n}=cn\log{n}$ and as $n^{\alpha-1}$, $1, Comment: arXiv admin note: substantial text overlap with arXiv:2205.03328

In federated learning (FL), a machine learning (ML) model is collectively trained by a large number of users, using their private data in their local devices. With top $r$ sparsification in FL, the users only upload the most significant $r$ fraction of updates, and the servers only send the most significant $r'$ fraction of parameters to the users in order to reduce the communication cost. However, the values and the indices of the sparse updates leak information about the users' private data. In this work, we consider an FL setting where $N$ non-colluding databases store the model to be trained, from which the users download and update sparse parameters privately, without revealing the values of the updates or their indices to the databases. We propose four schemes with different properties to perform this task while achieving the minimum communication costs, and show that the information theoretic privacy of both values and positions of the sparse updates can be guaranteed. This is achieved at a considerable storage cost, though. To alleviate this, we generalize the schemes in such a way that the storage cost is reduced at the expense of a certain amount of information leakage, using a model segmentation mechanism. In general, we provide the tradeoff between communication cost, storage cost and information leakage in private FL with top $r$ sparsification., arXiv admin note: substantial text overlap with arXiv:2212.09704, arXiv:2212.11947

We consider a network consisting of $n$ nodes that aim to track a continually updating process or event. To disseminate updates about the event to the network, two sources are available, such that information obtained from one source is considered more reliable than the other source. The nodes wish to have access to information about the event that is not only latest but also more reliable, and prefer a reliable packet over an unreliable packet even when the former is a bit outdated with respect to the latter. We study how such preference affects the fraction of users with reliable information in the network and their version age of information. We derive the analytical equations to characterize the two quantities, long-term expected fraction of nodes with reliable packets and their long-term expected version age using stochastic hybrid systems (SHS) modelling and study their properties. We also compare these results with the case where nodes give more preference to freshness of information than its reliability. Finally we show simulation results to verify the theoretical results and shed further light on behavior of above quantities with respect to dependent variables.

We study age of information in multi-hop multi-cast cache-enabled networks where the inter-update times on the links are not necessarily exponentially distributed. We focus on the set of non-arithmetic distributions for inter-update times, which includes continuous probability distributions as a subset. We first characterize instantaneous age of information at each node for arbitrary networks. We then explicate the recursive equations for instantaneous age of information in multi-hop networks and derive closed form expressions for expected age of information at an end-user. We show that expected age in multi-hop networks exhibits an additive structure. Further, we show that the expected age at each user is directly proportional to the variance of inter-update times at all links between a user and the source. We expect the analysis in this work to help alleviate the over-dependence on Poisson processes for future work in age of information.

We consider the federated submodel learning (FSL) problem and propose an approach where clients are able to update the central model information theoretically privately. Our approach is based on private set union (PSU), which is further based on multi-message symmetric private information retrieval (MM-SPIR). The server has two non-colluding databases which keep the model in a replicated manner. With our scheme, the server does not get to learn anything further than the subset of submodels updated by the clients: the server does not get to know which client updated which submodel(s), or anything about the local client data. In comparison to the state-of-the-art private FSL schemes of Jia-Jafar and Vithana-Ulukus, our scheme does not require noisy storage of the model at the databases; and in comparison to the secure aggregation scheme of Zhao-Sun, our scheme does not require pre-distribution of client-side common randomness, instead, our scheme creates the required client-side common randomness via random SPIR and one-time pads. The protocol starts with a common randomness generation (CRG) phase where the two databases establish common randomness at the client-side using RSPIR and one-time pads (this phase is called FSL-CRG). Next, the clients utilize the established client-side common randomness to have the server determine privately the union of indices of submodels to be updated collectively by the clients (this phase is called FSL-PSU). Then, the two databases broadcast the current versions of the submodels in the set union to clients. The clients update the submodels based on their local training data. Finally, the clients use a variation of FSL-PSU to write the updates back to the databases privately (this phase is called FSL-write). Our proposed private FSL scheme is robust against client drop-outs, client late-arrivals, and database drop-outs.

This paper studies the notion of age in task-oriented communications that aims to execute a task at a receiver utilizing the data at its transmitter. The transmitter-receiver operations are modeled as an encoder-decoder pair that is jointly trained while considering channel effects. The encoder converts data samples into feature vectors of small dimension and transmits them with a small number of channel uses thereby reducing the number of transmissions and latency. Instead of reconstructing input samples, the decoder performs a task, e.g., classification, on the received signals. Applying different deep neural networks of encoder-decoder pairs on MNIST and CIFAR-10 image datasets, the classifier accuracy is shown to increase with the number of channel uses at the expense of longer service time. The peak age of task information (PAoTI) is introduced to analyze this accuracy-latency tradeoff when the age grows unless a received signal is classified correctly. By incorporating channel and traffic effects, design guidelines are obtained for task-oriented communications by characterizing how the PAoTI first decreases and then increases with the number of channel uses. A dynamic update mechanism is presented to adapt the number of channel uses to channel and traffic conditions, and reduce the PAoTI in task-oriented communications.

We consider a time slotted communication system consisting of a base station (BS) and a user. At each time slot an update packet arrives at the BS with probability $p$, and the BS successfully transmits the update packet with probability $q$ over an erasure channel. We assume that the BS has a unit size buffer where it can store an update packet upon paying a storage cost $c$. There is a trade-off between the age of information and the storage cost. We formulate this trade-off as a Markov decision process and find an optimal switching type storage policy.

We consider the federated submodel learning (FSL) problem in a distributed storage system. In the FSL framework, the full learning model at the server side is divided into multiple submodels such that each selected client needs to download only the required submodel(s) and upload the corresponding update(s) in accordance with its local training data. The server comprises multiple independent databases and the full model is stored across these databases. An eavesdropper passively observes all the storage and listens to all the communicated data, of its controlled databases, to gain knowledge about the remote client data and the submodel information. In addition, a subset of databases may fail, negatively affecting the FSL process, as FSL process may take a non-negligible amount of time for large models. To resolve these two issues together (i.e., security and database repair), we propose a novel coding mechanism coined ramp secure regenerating coding (RSRC), to store the full model in a distributed manner. Using our new RSRC method, the eavesdropper is permitted to learn a controllable amount of submodel information for the sake of reducing the communication and storage costs. Further, during the database repair process, in the construction of the replacement database, the submodels to be updated are stored in the form of their latest version from updating clients, while the remaining submodels are obtained from the previous version in other databases through routing clients. Our new RSRC-based distributed FSL approach is constructed on top of our earlier two-database FSL scheme which uses private set union (PSU). A complete one-round FSL process consists of FSL-PSU phase, FSL-write phase and additional auxiliary phases. Our proposed FSL scheme is also robust against database drop-outs, client drop-outs, client late-arrivals and an active adversary controlling databases.

We introduce the problem of deceptive information retrieval (DIR), in which a user wishes to download a required file out of multiple independent files stored in a system of databases while \emph{deceiving} the databases by making the databases' predictions on the user-required file index incorrect with high probability. Conceptually, DIR is an extension of private information retrieval (PIR). In PIR, a user downloads a required file without revealing its index to any of the databases. The metric of deception is defined as the probability of error of databases' prediction on the user-required file, minus the corresponding probability of error in PIR. The problem is defined on time-sensitive data that keeps updating from time to time. In the proposed scheme, the user deceives the databases by sending \emph{real} queries to download the required file at the time of the requirement and \emph{dummy} queries at multiple distinct future time instances to manipulate the probabilities of sending each query for each file requirement, using which the databases' make the predictions on the user-required file index. The proposed DIR scheme is based on a capacity achieving probabilistic PIR scheme, and achieves rates lower than the PIR capacity due to the additional downloads made to deceive the databases. When the required level of deception is zero, the proposed scheme achieves the PIR capacity.

We consider a fully-connected wireless gossip network which consists of a source and $n$ receiver nodes. The source updates itself with a Poisson process and also sends updates to the nodes as Poisson arrivals. Upon receiving the updates, the nodes update their knowledge about the source. The nodes gossip the data among themselves in the form of Poisson arrivals to disperse their knowledge about the source. The total gossiping rate is bounded by a constraint. The goal of the network is to be as timely as possible with the source. We propose a scheme which we coin \emph{age sense updating multiple access in networks (ASUMAN)}, which is a distributed opportunistic gossiping scheme, where after each time the source updates itself, each node waits for a time proportional to its current age and broadcasts a signal to the other nodes of the network. This allows the nodes in the network which have higher age to remain silent and only the low-age nodes to gossip, thus utilizing a significant portion of the constrained total gossip rate. We calculate the average age for a typical node in such a network with symmetric settings, and show that the theoretical upper bound on the age scales as $O(1)$. ASUMAN, with an average age of $O(1)$, offers significant gains compared to a system where the nodes just gossip blindly with a fixed update rate, in which case the age scales as $O(\log n)$. Further, we analyzed the performance of ASUMAN for fractional, finitely connected, sublinear and hierarchical cluster networks. Finally, we show that the $O(1)$ age scaling can be extended to asymmetric settings as well. We give an example of power law arrivals, where nodes' ages scale differently but follow the $O(1)$ bound., Comment: arXiv admin note: substantial text overlap with arXiv:2207.07094

We study the version age of information in a multi-hop multi-cast cache-enabled network, where updates at the source are marked with incrementing version numbers, and the inter-update times on the links are not necessarily exponentially distributed. We focus on the set of non-arithmetic distributions, which includes continuous probability distributions as a subset, with finite first and second moments for inter-update times. We first characterize the instantaneous version age of information at each node for an arbitrary network. We then explicate the recursive equations for instantaneous version age of information in multi-hop networks and employ semi-martingale representation of renewal processes to derive closed form expressions for the expected version age of information at an end user. We show that the expected age in a multi-hop network exhibits an additive structure. Further, we show that the expected age at each user is proportional to the variance of inter-update times at all links between a user and the source. Thus, end user nodes should request packet updates at constant intervals., Comment: arXiv admin note: substantial text overlap with arXiv:2301.13830

We consider gossiping in a fully-connected wireless network consisting of $n$ nodes. The network receives Poisson updates from a source, which generates new information. The nodes gossip their available information with the neighboring nodes to maintain network timeliness. In this work, we propose two gossiping schemes, one semi-distributed and the other one fully-distributed. In the semi-distributed scheme, the freshest nodes use pilot signals to interact with the network and gossip with the full available update rate $B$. In the fully-distributed scheme, each node gossips for a fixed amount of time duration with the full update rate $B$. Both schemes achieve $O(1)$ age scaling, and the semi-distributed scheme has the best age performance for any symmetric randomized gossiping policy. We compare the results with the recently proposed ASUMAN scheme, which also gives $O(1)$ age performance, but the nodes need to be age-aware.

We investigate the problem of private read update write (PRUW) with heterogeneous storage constrained databases in federated submodel learning (FSL). In FSL a machine learning (ML) model is divided into multiple submodels based on different types of data used to train it. A given user downloads, updates and uploads the updates back to a single submodel of interest, based on the type of user's local data. With PRUW, the process of reading (downloading) and writing (uploading) is carried out such that information theoretic privacy of the updating submodel index and the values of updates is guaranteed. We consider the practical scenario where the submodels are stored in databases with arbitrary (heterogeneous) storage constraints, and provide a PRUW scheme with a storage mechanism that utilizes submodel partitioning and encoding to minimize the communication cost.

We consider a communication system where a base station (BS) transmits update packets to $N$ users, one user at a time, over a wireless channel. We investigate the age of this status updating system with an adversary that jams the update packets in the downlink. We consider two system models: with diversity and without diversity. In the model without diversity, we show that if the BS schedules the users with a stationary randomized policy, then the optimal choice for the adversary is to block the user which has the lowest probability of getting scheduled by the BS, at the middle of the time horizon, consecutively for $\alpha T$ time slots. In the model with diversity, we show that for large $T$, the uniform user scheduling algorithm together with the uniform sub-carrier choosing algorithm is $\frac{2 N_{sub}}{N_{sub}-1}$ optimal. Next, we investigate the game theoretic equilibrium points of this status updating system. For the model without diversity, we show that a Nash equilibrium does not exist, however, a Stackelberg equilibrium exists when the scheduling algorithm of the BS acts as the leader and the adversary acts as the follower. For the model with diversity, we show that a Nash equilibrium exists and identify the Nash equilibrium. Finally, we extend the model without diversity to the case where the BS can serve multiple users and the adversary can jam multiple users, at a time., Comment: arXiv admin note: substantial text overlap with arXiv:2202.04050, arXiv:2202.05233

We consider gossip networks consisting of a source that maintains the current version of a file, $n$ nodes that use asynchronous gossip mechanisms to disseminate fresh information in the network, and an oblivious adversary who infects the packets at a target node through data timestamp manipulation, with the intent to replace circulation of fresh packets with outdated packets in the network. We demonstrate how network topology capacitates an adversary to influence age scaling in a network. We show that in a fully connected network, a single infected node increases the expected age from $O(\log n)$ to $O(n)$. Further, we show that the optimal behavior for an adversary is to reset the timestamps of all outgoing packets to the current time and of all incoming packets to an outdated time for the infected node; thereby preventing any fresh information to go into the infected node, and facilitating acceptance of stale information out of the infected node into other network nodes. Lastly for fully connected network, we show that if an infected node contacts only a single node instead of all nodes of the network, the system age can still be degraded to $O(n)$. These show that fully connected nature of a network can be both a benefit and a detriment for information freshness; full connectivity, while enabling fast dissemination of information, also enables fast dissipation of adversarial inputs. We then analyze the unidirectional ring network, the other end of the network connectivity spectrum, where we show that the adversarial effect on age scaling of a node is limited by its distance from the adversary, and the age scaling for a large fraction of the network continues to be $O(\sqrt{n})$, unchanged from the case with no adversary. We finally support our findings with simulations., arXiv admin note: substantial text overlap with arXiv:2205.08510

Semantic communications seeks to transfer information from a source while conveying a desired meaning to its destination. We model the transmitter-receiver functionalities as an autoencoder followed by a task classifier that evaluates the meaning of the information conveyed to the receiver. The autoencoder consists of an encoder at the transmitter to jointly model source coding, channel coding, and modulation, and a decoder at the receiver to jointly model demodulation, channel decoding and source decoding. By augmenting the reconstruction loss with a semantic loss, the two deep neural networks (DNNs) of this encoder-decoder pair are interactively trained with the DNN of the semantic task classifier. This approach effectively captures the latent feature space and reliably transfers compressed feature vectors with a small number of channel uses while keeping the semantic loss low. We identify the multi-domain security vulnerabilities of using the DNNs for semantic communications. Based on adversarial machine learning, we introduce test-time (targeted and non-targeted) adversarial attacks on the DNNs by manipulating their inputs at different stages of semantic communications. As a computer vision attack, small perturbations are injected to the images at the input of the transmitter's encoder. As a wireless attack, small perturbations signals are transmitted to interfere with the input of the receiver's decoder. By launching these stealth attacks individually or more effectively in a combined form as a multi-domain attack, we show that it is possible to change the semantics of the transferred information even when the reconstruction loss remains low. These multi-domain adversarial attacks pose as a serious threat to the semantics of information transfer (with larger impact than conventional jamming) and raise the need of defense methods for the safe adoption of semantic communications.

Multi-task learning (MTL) is a learning paradigm to learn multiple related tasks simultaneously with a single shared network where each task has a distinct personalized header network for fine-tuning. MTL can be integrated into a federated learning (FL) setting if tasks are distributed across clients and clients have a single shared network, leading to personalized federated learning (PFL). To cope with statistical heterogeneity in the federated setting across clients which can significantly degrade the learning performance, we use a distributed dynamic weighting approach. To perform the communication between the remote parameter server (PS) and the clients efficiently over the noisy channel in a power and bandwidth-limited regime, we utilize over-the-air (OTA) aggregation and hierarchical federated learning (HFL). Thus, we propose hierarchical over-the-air (HOTA) PFL with a dynamic weighting strategy which we call HOTA-FedGradNorm. Our algorithm considers the channel conditions during the dynamic weight selection process. We conduct experiments on a wireless communication system dataset (RadComDynamic). The experimental results demonstrate that the training speed with HOTA-FedGradNorm is faster compared to the algorithms with a naive static equal weighting strategy. In addition, HOTA-FedGradNorm provides robustness against the negative channel effects by compensating for the channel conditions during the dynamic weight selection process.

We improve security-latency bounds of Nakamoto consensus by analyzing the race between adversarial and honest chains in three different phases: pre-mining, confirmation and post-confirmation. We find the probability distribution of the length of the adversarial chain and the rigged adversarial chain under jumper models during the confirmation interval. We analyze certain properties of this race to model pre-mining and post-confirmation phases with random walks that provide tighter bounds than existing results. Combining all three phases provides novel upper and lower bounds for blockchains with small $\lambda\Delta$.

We investigate the problem of private read update write (PRUW) in federated submodel learning (FSL) with sparsification. In FSL, a machine learning model is divided into multiple submodels, where each user updates only the submodel that is relevant to the user's local data. PRUW is the process of privately performing FSL by reading from and writing to the required submodel without revealing the submodel index, or the values of updates to the databases. Sparsification is a widely used concept in learning, where the users update only a small fraction of parameters to reduce the communication cost. Revealing the coordinates of these selected (sparse) updates leaks privacy of the user. We show how PRUW in FSL can be performed with sparsification. We propose a novel scheme which privately reads from and writes to arbitrary parameters of any given submodel, without revealing the submodel index, values of updates, or the coordinates of the sparse updates, to databases. The proposed scheme achieves significantly lower reading and writing costs compared to what is achieved without sparsification.

We consider a system with a source which maintains the most current version of a file, and a ring network of $n$ user nodes that wish to acquire the latest version of the file. The source gets updated with newer file versions as a point process, and forwards them to the user nodes, which further forward them to their neighbors using a memoryless gossip protocol. We study the average version age of this network in the presence of $\tilde{n}$ jammers that disrupt inter-node communications. To this purpose, we construct an alternate system model of mini-rings and prove that the version age of the original model can be sandwiched between constant multiples of the version age of the alternate model. We show that when the number of jammers scales as a fractional power of the network size, i.e., $\tilde n= cn^\alpha$, the version age scales as $\sqrt{n}$ when $\alpha < \frac{1}{2}$, and as $n^{\alpha}$ when $\alpha \geq \frac{1}{2}$. As the version age of a ring network without any jammers scales as $\sqrt{n}$, our result implies that the version age with gossiping is robust against up to $\sqrt{n}$ jammers in a ring network.

We consider the total (upload plus download) communication cost of two-database symmetric private information retrieval (SPIR) through its relationship to conditional disclosure of secrets (CDS). In SPIR, a user wishes to retrieve a message out of $K$ messages from $N$ non-colluding and replicated databases without learning anything beyond the retrieved message, while no individual database learns the retrieved message index. In CDS, two parties each holding an individual input and sharing a common secret wish to disclose this secret to an external party in an efficient manner if and only if their inputs satisfy a public deterministic function. As a natural extension of CDS, we introduce conditional disclosure of multiple secrets (CDMS) where two parties share multiple i.i.d.~common secrets rather than a single common secret as in CDS. We show that a special configuration of CDMS is equivalent to two-database SPIR. Inspired by this equivalence, we design download cost efficient SPIR schemes using bipartite graph representation of CDS and CDMS, and determine the exact minimum total communication cost of $N=2$ database SPIR for $K=3$ messages.

We investigate the problem of private read update write (PRUW) in relation to federated submodel learning (FSL) with storage constrained databases. In PRUW, a user privately reads a submodel from a system of $N$ databases containing $M$ submodels, updates it locally, and writes the update back to the databases without revealing the submodel index or the value of the update. The databases considered in this problem are only allowed to store a given amount of information specified by an arbitrary storage constraint. We provide a storage mechanism that determines the contents of each database prior to the application of the PRUW scheme, such that the total communication cost is minimized. We show that the proposed storage scheme achieves a lower total cost compared to what is achieved by using \emph{coded storage} or \emph{divided storage} to meet the given storage constraint.

We investigate the game theoretic equilibrium points of a status updating system with an adversary that jams the updates in the downlink. We consider the system models with and without diversity. The adversary can jam up to $\alpha$ proportion of the entire communication window. In the model without diversity, in each time slot, the base station schedules a user from $N$ users according to a stationary distribution. The adversary blocks (jams) $\alpha T$ time slots of its choosing out of the total $T$ time slots. For this system, we show that a Nash equilibrium does not exist, however, a Stackelberg equilibrium exists when the scheduling algorithm of the base station acts as the leader and the adversary acts as the follower. In the model with diversity, in each time slot, the base station schedules a user from $N$ users and chooses a sub-carrier from $N_{sub}$ sub-carriers to transmit update packets to the scheduled user according to a stationary distribution. The adversary blocks $\alpha T$ time slots of its choosing out of $T$ time slots at the sub-carriers of its choosing. For this system, we show that a Nash equilibrium exists and identify the Nash equilibrium.

In status update systems, multiple features carried by the status updating process require pursuit of objectives beyond timeliness measured by the age of information of updates. We consider such a problem where the transmitter sends status update messages through a noiseless binary energy harvesting channel that is equivalent to a timing channel. The transmitter aims to amplify or mask the energy state information that is carried in the updating process. The receiver extracts encoded information, infers the energy state sequence while maintaining timeliness of status updates. Consequently, the timings of the updates must be designed to control the message rate, the energy state uncertainty, and the age of information. We investigate this three-way trade-off between the achievable rate, the reduction in energy arrival state uncertainty, and the age of information, for zero and infinite battery cases.

We consider a system consisting of a large network of $n$ users and a library of files, wherein inter-user communication is established based upon gossip mechanisms. Each file is initially present at exactly one node, which is designated as the file \emph{source}. The source gets updated with newer versions of the file according to an arbitrary distribution in real time, and the other users in the network wish to acquire the latest possible version of the file. We present a class of gossip protocols that achieve $O(1)$ age at a typical node in a single-file system and $O(n)$ age at a typical node for a given file in an $n$-file system. We show that file slicing and network coding based protocols fall under the presented class of protocols. Numerical evaluation results are presented to confirm the aforementioned bounds.

We introduce the problem of random symmetric private information retrieval (RSPIR). In canonical PIR, a user downloads a message out of $K$ messages from $N$ non-colluding and replicated databases in such a way that no database can know which message the user has downloaded (user privacy). In SPIR, the privacy is symmetric, in that, not only that the databases cannot know which message the user has downloaded, the user itself cannot learn anything further than the particular message it has downloaded (database privacy). In RSPIR, different from SPIR, the user does not have an input to the databases, i.e., the user does not pick a specific message to download, instead is content with any one of the messages. In RSPIR, the databases need to send symbols to the user in such a way that the user is guaranteed to download a message correctly (random reliability), the databases do not know which message the user has received (user privacy), and the user does not learn anything further than the one message it has received (database privacy). This is the digital version of a blind box, also known as gachapon, which implements the above specified setting with physical objects for entertainment. This is also the blind version of $1$-out-of-$K$ oblivious transfer (OT), an important cryptographic primitive. We study the information-theoretic capacity of RSPIR for the case of $N=2$ databases. We determine its exact capacity for the cases of $K = 2, 3, 4$ messages. While we provide a general achievable scheme that is applicable to any number of messages, the capacity for $K\geq 5$ remains open.

We consider dynamical group testing problem with a community structure. With a discrete-time SIR (susceptible, infectious, recovered) model, we use Dorfman's two-step group testing approach to identify infections, and step in whenever necessary to inhibit infection spread via quarantines. We analyze the trade-off between quarantine and test costs as well as disease spread. For the special dynamical i.i.d. model, we show that the optimal first stage Dorfman group size differs in dynamic and static cases. We compare the performance of the proposed dynamic two-stage Dorfman testing with state-of-the-art non-adaptive group testing method in dynamic settings.

We investigate the problem of private read update write (PRUW) in relation to private federated submodel learning (FSL), where a machine learning model is divided into multiple submodels based on the different types of data used to train the model. In PRUW, each user downloads the required submodel without revealing its index in the reading phase, and uploads the updates of the submodel without revealing the submodel index or the values of the updates in the writing phase. In this work, we first provide a basic communication efficient PRUW scheme, and study further means of reducing the communication cost via sparsification. Gradient sparsification is a widely used concept in learning applications, where only a selected set of parameters is downloaded and updated, which significantly reduces the communication cost. In this paper, we study how the concept of sparsification can be incorporated in private FSL with the goal of reducing the communication cost, while guaranteeing information theoretic privacy of the updated submodel index as well as the values of the updates. To this end, we introduce two schemes: PRUW with top $r$ sparsification and PRUW with random sparsification. The former communicates only the most significant parameters/updates among the servers and the users, while the latter communicates a randomly selected set of parameters/updates. The two proposed schemes introduce novel techniques such as parameter/update (noisy) permutations to handle the additional sources of information leakage in PRUW caused by sparsification. Both schemes result in significantly reduced communication costs compared to that of the basic (non-sparse) PRUW scheme., Comment: arXiv admin note: text overlap with arXiv:2205.15992

We investigate the trade-off between rate, privacy and storage in federated learning (FL) with top $r$ sparsification, where the users and the servers in the FL system only share the most significant $r$ and $r'$ fractions, respectively, of updates and parameters in the FL process, to reduce the communication cost. We present schemes that guarantee information theoretic privacy of the values and indices of the sparse updates sent by the users at the expense of a larger storage cost. To this end, we generalize the scheme to reduce the storage cost by allowing a certain amount of information leakage. Thus, we provide the general trade-off between the communication cost, storage cost, and information leakage in private FL with top $r$ sparsification, along the lines of two proposed schemes.

Communications systems to date are primarily designed with the goal of reliable transfer of digital sequences (bits). Next generation (NextG) communication systems are beginning to explore shifting this design paradigm to reliably executing a given task such as in task-oriented communications. In this paper, wireless signal classification is considered as the task for the NextG Radio Access Network (RAN), where edge devices collect wireless signals for spectrum awareness and communicate with the NextG base station (gNodeB) that needs to identify the signal label. Edge devices may not have sufficient processing power and may not be trusted to perform the signal classification task, whereas the transfer of signals to the gNodeB may not be feasible due to stringent delay, rate, and energy restrictions. Task-oriented communications is considered by jointly training the transmitter, receiver and classifier functionalities as an encoder-decoder pair for the edge device and the gNodeB. This approach improves the accuracy compared to the separated case of signal transfer followed by classification. Adversarial machine learning poses a major security threat to the use of deep learning for task-oriented communications. A major performance loss is shown when backdoor (Trojan) and adversarial (evasion) attacks target the training and test processes of task-oriented communications.

Decentralized and federated learning algorithms face data heterogeneity as one of the biggest challenges, especially when users want to learn a specific task. Even when personalized headers are used concatenated to a shared network (PF-MTL), aggregating all the networks with a decentralized algorithm can result in performance degradation as a result of heterogeneity in the data. Our algorithm uses exchanged gradients to calculate the correlations among tasks automatically, and dynamically adjusts the communication graph to connect mutually beneficial tasks and isolate those that may negatively impact each other. This algorithm improves the learning performance and leads to faster convergence compared to the case where all clients are connected to each other regardless of their correlations. We conduct experiments on a synthetic Gaussian dataset and a large-scale celebrity attributes (CelebA) dataset. The experiment with the synthetic data illustrates that our proposed method is capable of detecting tasks that are positively and negatively correlated. Moreover, the results of the experiments with CelebA demonstrate that the proposed method may produce significantly faster training results than fully-connected networks.

We consider adversarial machine learning based attacks on power allocation where the base station (BS) allocates its transmit power to multiple orthogonal subcarriers by using a deep neural network (DNN) to serve multiple user equipments (UEs). The DNN that corresponds to a regression model is trained with channel gains as the input and returns transmit powers as the output. While the BS allocates the transmit powers to the UEs to maximize rates for all UEs, there is an adversary that aims to minimize these rates. The adversary may be an external transmitter that aims to manipulate the inputs to the DNN by interfering with the pilot signals that are transmitted to measure the channel gain. Alternatively, the adversary may be a rogue UE that transmits fabricated channel estimates to the BS. In both cases, the adversary carefully crafts adversarial perturbations to manipulate the inputs to the DNN of the BS subject to an upper bound on the strengths of these perturbations. We consider the attacks targeted on a single UE or all UEs. We compare these attacks with a benchmark, where the adversary scales down the input to the DNN. We show that the adversarial attacks are much more effective than the benchmark attack in terms of reducing the rate of communications. We also show that adversarial attacks are robust to the uncertainty at the adversary including the erroneous knowledge of channel gains and the potential errors in exercising the attacks exactly as specified.

We determine the exact sum secure degrees of freedom (d.o.f.) of the K-user Gaussian interference channel. We consider three different secrecy constraints: 1) K-user interference channel with one external eavesdropper (IC-EE), 2) K-user interference channel with confidential messages (IC-CM), and 3) K-user interference channel with confidential messages and one external eavesdropper (IC-CM-EE). We show that for all of these three cases, the exact sum secure d.o.f. is K(K-1)/(2K-1). We show converses for IC-EE and IC-CM, which imply a converse for IC-CM-EE. We show achievability for IC-CM-EE, which implies achievability for IC-EE and IC-CM. We develop the converses by relating the channel inputs of interfering users to the reliable rates of the interfered users, and by quantifying the secrecy penalty in terms of the eavesdroppers' observations. Our achievability uses structured signaling, structured cooperative jamming, channel prefixing, and asymptotic real interference alignment. While the traditional interference alignment provides some amount of secrecy by mixing unintended signals in a smaller sub-space at every receiver, in order to attain the optimum sum secure d.o.f., we incorporate structured cooperative jamming into the achievable scheme, and intricately design the structure of all of the transmitted signals jointly., Submitted to IEEE Transactions on Information Theory, May 2013

This document is withdrawn due to an error in Lemma 4., Comment: This document is withdrawn due to an error in Lemma 4

In this paper, we propose a new coding scheme for the general relay channel. This coding scheme is in the form of a block Markov code. The transmitter uses a superposition Markov code. The relay compresses the received signal and maps the compressed version of the received signal into a codeword conditioned on the codeword of the previous block. The receiver performs joint decoding after it has received all of the B blocks. We show that this coding scheme can be viewed as a generalization of the well-known Compress-And-Forward (CAF) scheme proposed by Cover and El Gamal. Our coding scheme provides options for preserving the correlation between the channel inputs of the transmitter and the relay, which is not possible in the CAF scheme. Thus, our proposed scheme may potentially yield a larger achievable rate than the CAF scheme., 23 pages, 1 figure, submitted to IEEE Trans. on Information Theory

We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. The overall goal of the sensor network is to take measurements from an underlying random process, code and transmit those measurement samples to a collector node in a cooperative multiple access channel with potential feedback, and reconstruct the entire random process at the collector node. We provide lower and upper bounds for the minimum achievable expected distortion when the underlying random process is Gaussian. When the Gaussian random process satisfies some general conditions, we evaluate the lower and upper bounds explicitly, and show that they are of the same order for a wide range of power constraints. Thus, for these random processes, under these power constraints, we express the minimum achievable expected distortion as a function of the power constraint. Further, we show that the achievability scheme that achieves the lower bound on the distortion is a separation-based scheme that is composed of multi-terminal rate-distortion coding and amplify-and-forward channel coding. Therefore, we conclude that separation is order-optimal for the dense Gaussian sensor network scenario under consideration, when the underlying random process satisfies some general conditions., submitted to IEEE Transactions on Information Theory

For a fading Gaussian multiple access channel with user cooperation, we obtain the optimal power allocation policies that maximize the rates achievable by block Markov superposition coding. The optimal policies result in a coding scheme that is simpler than the one for a general multiple access channel with generalized feedback. This simpler coding scheme also leads to the possibility of formulating an otherwise non-concave optimization problem as a concave one. Using the channel state information at the transmitters to adapt the powers, we demonstrate significant gains over the achievable rates for existing cooperative systems., Submitted to IEEE Transactions on Wireless Communications, October 2005

We investigate the behavior of two users and one jammer in an AWGN channel with and without fading when they participate in a non-cooperative zero-sum game, with the channel's input/output mutual information as the objective function. We assume that the jammer can eavesdrop the channel and can use the information obtained to perform correlated jamming. Under various assumptions on the channel characteristics, and the extent of information available at the users and the jammer, we show the existence, or otherwise non-existence of a simultaneously optimal set of strategies for the users and the jammer. In all the cases where the channel is non-fading, we show that the game has a solution, and the optimal strategies are Gaussian signalling for the users and linear jamming for the jammer. In fading channels, we envision each player's strategy as a power allocation function over the channel states, together with the signalling strategies at each channel state. We reduce the game solution to a set of power allocation functions for the players and show that when the jammer is uncorrelated, the game has a solution, but when the jammer is correlated, a set of simultaneously optimal power allocation functions for the users and the jammer does not always exist. In this case, we characterize the max-min user power allocation strategies and the corresponding jammer power allocation strategy., Submitted to IEEE Transactions on Information Theory