Multi-Byzantine Fault Tolerant (Multi-BFT) consensus, which runs multiple BFT instances in parallel, has recently emerged as a promising approach to overcome the leader bottleneck in classical BFT protocols. However, existing designs rely on a global ordering layer to serialize blocks across instances, an intuitive yet costly mechanism that constrains scalability, amplifies failure propagation, and complicates deployment. In this paper, we challenge this conventional wisdom. We present HYDRA, the first Multi-BFT consensus framework that eliminates global ordering altogether. HYDRA introduces an object-centric execution model that partitions transactions by their accessed objects, enabling concurrent yet deterministic execution across instances. To ensure consistency, HYDRA combines lightweight lock-based coordination with a deadlock resolution mechanism, achieving both scalability and correctness. We implement HYDRA and evaluate it on up to 128 replicas in both LAN and WAN environments. Experimental results show HYDRA outperforms several state-of-the-art Multi-BFT protocols in the presence of a straggler. These results demonstrate strong consistency and high performance by removing global ordering, opening a new direction toward scalable Multi-BFT consensus design.

The proliferation of blockchain-backed cryptocurrencies has sparked the need for cross-chain exchanges of diverse digital assets. Unfortunately, current exchanges suffer from high on-chain verification costs, weak threat models of central trusted parties, or synchronous requirements, making them impractical for currency trading applications. In this paper, we present MERCURY, a practical cryptocurrency exchange that is trust-minimized and efficient without online-client requirements. MERCURY leverages Trusted Execution Environments (TEEs) to shield participants from malicious behaviors, eliminating the reliance on trusted participants and making on-chain verification efficient. Despite the simple idea, building a practical TEE-assisted cross-chain exchange is challenging due to the security and unavailability issues of TEEs. MERCURY tackles the unavailability problem of TEEs by implementing an efficient challenge-response mechanism executed on smart contracts. Furthermore, MERCURY utilizes a lightweight transaction verification mechanism and adopts multiple optimizations to reduce on-chain costs. Comparative evaluations with XClaim, ZK-bridge, and Tesseract demonstrate that MERCURY significantly reduces on-chain costs by approximately 67.87%, 45.01%, and 47.70%, respectively.

With the growing popularity of blockchains, modern chained BFT protocols combining chaining and leader rotation to obtain better efficiency and leadership democracy have received increasing interest. Although the efficiency provisions of chained BFT protocols have been thoroughly analyzed, the leadership democracy has received little attention in prior work. In this paper, we scrutinize the leadership democracy of four representative chained BFT protocols, especially under attack. To this end, we propose a unified framework with two evaluation metrics,i.e., chain quality and censorship resilience, and quantitatively analyze chosen protocols through the Markov Decision Process (MDP). With this framework, we further examine the impact of two key components,i.e., voting pattern and leader rotation, on leadership democracy. Our results indicate that leader rotation is not enough to provide the leadership democracy guarantee; an adversary could utilize the design,e.g., voting pattern, to deteriorate the leadership democracy significantly. Based on the analysis results, we propose customized countermeasures for three evaluated protocols to improve their leadership democracy with only slight protocol overhead and no change of consensus rules. We also discuss future directions toward building more democratic chained BFT protocols.

Multi-BFT consensus runs multiple leader-based consensus instances in parallel, circumventing the leader bottleneck of a single instance. However, it contains an Achilles' heel: the need to globally order output blocks across instances. Deriving this global ordering is challenging because it must cope with different rates at which blocks are produced by instances. Prior Multi-BFT designs assign each block a global index before creation, leading to poor performance.

Multi-Byzantine Fault Tolerant (Multi-BFT) consensus allows multiple consensus instances to run in parallel, resolving the leader bottleneck problem inherent in classic BFT consensus. However, the global ordering of Multi-BFT consensus enforces a strict serialized sequence of transactions, imposing additional confirmation latency and also limiting concurrency. In this paper, we introduce Orthrus, a Multi-BFT protocol that accelerates transaction confirmation through partial ordering while reserving global ordering for transactions requiring stricter sequencing. To this end, Orthrus strategically partitions transactions to maximize concurrency and ensure consistency. Additionally, it incorporates an escrow mechanism to manage interactions between partially and globally ordered transactions. We evaluated Orthrus through extensive experiments in realistic settings, deploying 128 replicas in WAN and LAN environments. Our findings demonstrate latency reductions of up to 87% in WAN compared to existing Multi-BFT protocols.

This paper introduces a novel framework for constructing algebraic lattices based on Construction-D, leveraging nested linear codes and prime ideals from algebraic number fields. We focus on the application of these lattices in block-fading (BF) channels, which are characterized by piecewise-constant fading across blocks of transmitted symbols. This approach results in a semi-systematic generator matrix, providing a structured foundation for high -dimensional lattice design for BF channels. The proposed Construction-D lattices exhibit the full diversity property, making them highly effective for error performance improvement. To address this, we develop an efficient decoding algorithm designed specifically for full-diversity Construction-D lattices. Simulations indicate that the proposed lattices notably enhance error performance compared to full-diversity Construction-A lattices, especially in high-diversity scenarios. Interestingly, the anticipated performance gain from increasing the number of nested code levels was only observed in the two-level case. We believe that this is due to the amplified impact of error propagation during successive cancellation at higher levels. These findings highlight the promise of Construction-D lattices as an effective and practical coding strategy for enhancing communication reliability in BF channels.

A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch - Pirare based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that zero storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of tree has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving 3 ×lower total storage and 1.5-3 ×lower computation and communication costs. Most notably, TreePIR has 8-160× lower setup time and its polylog-complexity indexing algorithm is 19–160 ×faster than PBC for trees of 210_224leaves.

This paper addresses data-driven replay attack detection on industrial control systems. The primary challenge in detection lies in distinguishing replayed sensor measurements from normal measurements using only time series data. This is tackled through a novel two-stage detection and verification framework. The first stage consists of continuous real-time monitoring of sensor measurement patterns using matrix profile based change-point detection, used to indicate a possibility of a replay attack. The second stage verifies the presence of a replay attack by introducing spatial features to newly defined time series data. This is implemented by generating spectrograms of the time series measurements using short-time Fourier transform. Then, the spectrograms are split into image frames to form temporal sequences, creating spatio-temporal features that distinguish replay attacks. To capture both the spatial and temporal features, we utilise a Convolutional Long Short-Term Memory (ConvLSTM) neural network and implement it in an autoencoder architecture, in order to analyse data patterns in an unsupervised manner, where the replay attack is detected based on the reconstruction error. We demonstrate the effectiveness of our framework in the detection of different replay attack scenarios using the Tennessee Eastman process benchmark simulation system/process.Note to Practitioners—This paper is motivated by the importance of cyberattack detection in industrial control systems that are essential for the stable operation of many practical applications, such as in chemical processing and manufacturing plants, and power and water distribution networks. Specifically, replay attack detection using data-driven methods is explored, eliminating the need for an accurate process model which may be tedious to obtain. However, the attack’s implementation using actual/valid operational data to replicate normal behaviour, makes it difficult to detect using basic data-driven methods, resulting in an increased likelihood of false alarms or missed detection. To address this challenge, a two-stage detection and verification framework is proposed. The first stage performs real-time monitoring of sensor measurements using change-point detection on time series data patterns. The second stage verifies the occurrence of a replay attack by introducing spatial features to newly defined time series data. This framework therefore eliminates false/missed detection, and offers practitioners a robust method to enhance security measures in industrial control systems, minimising the risks posed by malicious replay attacks.

Rollups have emerged as a promising approach to improving blockchains’ scalability by offloading transaction execution off-chain. Existing rollup solutions either leverage complex zero-knowledge proofs or optimistically assume execution correctness unless challenged. However, these solutions suffer from high gas costs and significant withdrawal delays, hindering their adoption in decentralized applications. This paper introducesTeeRollup, an efficient rollup protocol that leverages Trusted Execution Environments (TEEs) to achieve both low gas costs and short withdrawal delays. Sequencers (i.e., system participants) execute transactions within TEEs and upload signed execution results to the blockchain with confidential keys of TEEs. Unlike most TEE-assisted blockchain designs,TeeRollupadopts a practical threat model where the integrity and availability of TEEs may be compromised. To address these issues, we first introduce a distributed system of sequencers with heterogeneous TEEs, ensuring system security even if a certain proportion of TEEs are compromised. Second, we propose a challenge mechanism to solve the redeemability issue caused by TEE unavailability. Furthermore,TeeRollupincorporates Data Availability Providers (DAPs) to reduce on-chain storage overhead and uses a laziness penalty mechanism to regulate DAP behavior. We implement a prototype ofTeeRollupin Golang, using the Ethereum test network, Sepolia. Our experimental results indicate thatTeeRollupoutperforms zero-knowledge rollups (ZK-rollups), reducing on-chain verification costs by approximately 86% and withdrawal delays to a few minutes.

This paper presents a novel framework for constructing full-diversity algebraic lattices based on Construction-D, utilizing nested linear codesC1⊂ · · · ⊂Ca⊆ FpNand prime ideals from algebraic number fields of degree n. Focused on block-fading (BF) channels, this approach yields a semi-systematic generator matrix suited for high-dimensional lattice design. The resulting Construction-D lattices achieve full diversity, significantly enhancing error performance. Additionally, we develop a decoding algorithm tailored for these full-diversity lattices, achieving linear complexity relative to the lattice dimension. Simulations indicate that the proposed lattices notably enhance error performance compared to full-diversity Construction-A lattices in diversity-2 cases. Interestingly, unlike AWGN channels, the expected performance enhancement of Construction-D over Construction-A, resulting from an increased number of nested code levels, was observed only in the two-level and diversity-2 cases. This phenomenon is likely due to the compounded error propagation during successive cancellation at higher levels, further amplified by higher diversity orders. The omission of parity-check enforcement at the final code level—aimed at simplifying our decoding—restricts the diversity order from the maximum ofn·dmin(Ca) ton, limiting performance gains. Unraveling the core reasons behind this decoding behavior remains an open challenge. Nevertheless, these findings highlight the promise of full-diversity Construction-D lattices as an effective coding strategy for BF channels.

Chained HotStuff is a state-of-the-art Byzantine fault-tolerant protocol for building decentralized systems like blockchains. Although chained HotStuff has been widely adopted in many systems, its performance (e.g., throughput and latency) under attacks is still under-explored. In this paper, we develop a multi-metric evaluation framework to quantitatively analyze the performance of chained HotStuff with respect to its chain growth rate, chain quality, and latency. We propose several new attack strategies and evaluate their effects on the performance of chained HotStuff. Our analysis shows that the chain growth rate (resp, chain quality) of chained HotStuff under our attacks can drop to$4/9$(resp,$12/17$) of that without attacks when one-third of nodes are Byzantine. In addition, we use our framework to evaluate a variant of chained HotStuff, DiemBFT and find that some engineering optimizations render it more vulnerable to some attacks than the original chained HotStuff. Finally, we provide two countermeasures, i.e., broadcasting QCs and the longest chain rule, to thwart these attacks. Our analysis shows that the proposed countermeasures can significantly reduce the latency (almost half of that in chained HotStuff) and make it impossible for an attacker to lower the chain quality by simple attacks.

Sidechains allow transaction dissemination and execution outside the blockchain main network (i.e., the mainchain), enabling a scalable, efficient, and secure financial infrastructure for the Internet of Things (IoT) without trusting any central authority. Existing sidechains either have online requirements or rely on intensive computation on a central operator, which does not meet the needs of IoT for dynamic changes and high performance. This article proposes an alternative sidechain construction, called Cumulus, which meets the needs of IoT by leveraging the classic Byzantine fault-tolerant (BFT) consensus protocols, such as PBFT, that have commonly been applied in permissioned blockchains. Cumulus builds BFT-based sidechains atop public blockchains (e.g., Ethereum) using smart contracts and ensures the bidirectional safety of users’ assets. Cumulus sidechains periodically interact with the mainchain and submit checkpoints through representatives selected in an efficient and decentralized manner. The experiments show that Cumulus sidechains outperform rollup-based sidechains, and state-of-the-art sidechain constructions, achieving two and three orders of magnitude improvement in throughput and latency while retaining comparable operational cost.

The rapid development of radio access network (RAN) slicing and control- and user-plane separation (CUPS) has created a new paradigm for future networks, namely, CUPS-based RAN slicing. In this article, we formulate the utility optimization problems of the CUPS-based RAN slicing system and propose a Lyapunov-based deep reinforcement learning (L-DRL) framework to solve them. Specifically, we propose that the control plane (CP) and user plane (UP) slices should control their respective power and subcarrier resources. First, we provide coverage-driven slices in the CP for coverage control and data-driven slices in the UP for diverse user requests, where we consider the influence of coverage-driven slices on data-driven slices. Second, we define the system’s utilities as income minus cost, and we formulate the utility maximization problem of the UP as a mixed-integer nonlinear programming (MINLP) problem, which is NP-hard because it considers both continuous actions (densities deployment and power allocation) and discrete action (subcarrier allocation). Furthermore, we design an alternating optimization method for the CP and UP based on the densities of deployment. Finally, we develop a novel framework for mixed-action optimization problems and propose a specific Lyapunov-based asynchronous advantage actor–critic (L-A3C) algorithm. Simulation results demonstrate that our proposed Lyapunov-based A3C (L-A3C) algorithm outperforms the standard A3C algorithm in terms of the convergence while achieving higher performance than Lyapunov optimization. Moreover, our proposed CUPS-based RAN slicing scheme surpasses the benchmark RAN slicing schemes in terms of the achievable rate and delay.

Continuous variable quantum key distribution (CV-QKD) protocol has drawn much attention due to its compatibility with existing optical communication systems. In this paper, we propose a quaternary modulated CV-QKD protocol using displacement receivers and adopt the post-selection scheme to overcome the ‘3dB limit’. We first establish the model of displacement receiver for discriminating quaternary modulated coherent signals in a realistic situation. The performance of non-adaptive displacement receiver and multi-stage feedforward receiver are both investigated under different noises and device imperfections. To improve the receiver performance, we numerically optimize the displacement operation and check the quantum advantage of the displacement receivers over the classical homodyne detection. Then we analyze the security of the proposed CV-QKD protocol. The secret key rate is derived for both types of displacement receivers under the collective beam splitting attack. We also optimize the transmitted signal photons for different channel transmission efficiencies under practical system constraints. Numerical results shed light on the practical application of displacement receivers in CV-QKD protocols. This includes evaluating the necessity of optimizing the displacement and incorporating the feedforward structure in a displacement receiver according to different practical system limitations. Moreover, under higher channel transmission efficiency and increased receiver noise level, a larger coherent amplitude is required for transmitting signals to attain the maximum secret key rate.

he HotStuff protocol is a recent breakthrough in Byzantine Fault Tolerant (BFT) consensus that enjoys both responsiveness and linear view change by creatively adding a round to classic two-round BFT protocols like PBFT. Despite its great advantages, HotStuff has a few limitations. First, the additional round of communication during normal cases results in higher latency. Second, HotStuff is vulnerable to certain performance attacks, which can significantly deteriorate its throughput and latency. To address these limitations, we propose a new two-round BFT protocol called Fast-HotStuff, which enjoys responsiveness and efficient view change that is comparable to the linear view-change in terms of performance. Our Fast-HotStuff has lower latency and is more robust against the performance attacks that HotStuff is susceptible to.

Leader-based Byzantine fault-tolerant (BFT) consensus protocols used by permissioned blockchains have limited scalability and robustness. To alleviate the leader bottleneck in BFT consensus, we introduce Stratus, a robust shared mempool protocol that decouples transaction distribution from consensus. Our idea is to have replicas disseminate transactions in a distributed manner and have the leader only propose transaction ids. Stratus uses a provably available broadcast (PAB) protocol to ensure the availability of the referenced transactions. To deal with unbalanced load across replicas, Stratus adopts a distributed load balancing protocol.We implemented and evaluated Stratus by integrating it with state-of-the-art BFT-based blockchain protocols. Our evaluation of these protocols in both LAN and WAN settings shows that Stratus-based protocols achieve 5× to 20× higher throughput than their native counterparts in a network with hundreds of replicas. In addition, the performance of Stratus degrades gracefully in the presence of network asynchrony, Byzantine attackers, and unbalanced workloads.

This paper considers the problem of distributed lossy compression where the goal is to recover one or more linear combinations of the sources at the decoder, subject to distortion constraints. For certain configurations, it is known that codes with algebraic structure can outperform i.i.d. codebooks. For the special case of finite-alphabet sources, recent work has demonstrated how to incorporate joint typicality decoding alongside linear encoding and binning. This work takes a discretization approach to extend this rate region to include both integer- and real-valued sources. As a case study, the rate region is evaluated for the Gaussian case. The resulting joint-typicality-based rate region recovers and generalizes the best-known rate region for this scenario, based on lattice encoding and sequential decoding.

The collaborative edge and cloud computing system has emerged as a promising solution to fulfill the unprecedented high requirements of 5G application scenarios. Due to vendor variations, it is often difficult to manage hardware facilities in such a collaborative system. Moreover, the amount of data generated and tasks requested by end devices are increasing exponentially, which introduces storage and computation bottlenecks. To address these issues, a novel systematic framework called software-defined edge and cloud computing (SD-ECC) is designed to manage the underlying physical resources of edge and cloud layers via software. SD-ECC is combined with an erasure-coded storage system, for which a task scheduling problem is formulated by considering data access and task processing steps. Then, a joint data access and task processing (JDATP) algorithm is proposed to minimize the task response time including data access latency and task processing latency. A practical SD-ECC platform is developed on OpenStack, OpenDaylight, and Kubernetes to conduct experiments with real-world datasets. The experimental results demonstrate that our proposed JDATP algorithm can reduce 20.87% of the task response time and increase 14.16% of the remaining storage space on average by comparing it with alternative schemes.

In this paper, the performance of optimally displaced threshold detection (ODTD) for discriminating ternary coherent signals is theoretically investigated. We first establish the receiver model for ternary phase shift keying optical quantum communication system using Kennedy receiver with ODTD in a realistic situation. Then we analytically study the error probability for ODTD and formulate a joint optimization problem to minimize this error probability of detection, which is a challenging mixed-integer programming (MIP) problem due to the discreteness of the detection threshold. We then propose an efficient algorithm to tackle this MIP problem and design the displacement and the threshold on both detection branches. We also discuss the receiving scheme using ODTD in the case of unequal prior probabilities and optimize the signal power distribution between the two branches. Numerical results show that for the discrimination of ternary coherent signals using Kennedy-type receiver, ODTD can mitigate the influence of thermal noise and dark count noise and is robust to imperfect quantum efficiency. Besides, we find that the error probability performance can be improved by optimizing the decoding order of the ternary signals and the reflectance of the beam splitter.

Researchers have discovered a series of theoretical attacks against Bitcoin's Nakamoto consensus; the most damaging ones are selfish mining, double-spending, and consistency delay attacks. These attacks have one common cause: block withholding. This paper proposes Crystal, which leverages quorum certificates to resist block withholding misbehavior. Crystal continuously elects committees from miners and requires each block to have a quorum certificate, i.e., a set of signatures issued by members of its committee. Consequently, an attacker has to publish its blocks to obtain quorum certificates, rendering block withholding impossible. To build Crystal, we design a novel two-round committee election in a Sybil-resistant, unpredictable and non-interactive way, and a reward mechanism to incentivize miners to follow the protocol. Our analysis and evaluations show that Crystal can significantly mitigate selfish mining and double-spending attacks. For example, in Bitcoin, an attacker with 30% of the total computation power will succeed in double-spending attacks with a probability of 15.6% to break the 6-confirmation rule; however, in Crystal, the success probability for the same attacker falls to 0.62%. We provide formal end-to-end safety proofs for Crystal, ensuring no unknown attacks will be introduced. To the best of our knowledge, Crystal is the first protocol that prevents selfish mining and double-spending attacks while providing safety proof.

Distributed computing, in which a resource-intensive task is divided into subtasks and distributed among different machines, plays a key role in solving large-scale problems.Coded computingis a recently emerging paradigm where redundancy for distributed computing is introduced to alleviate the impact of slow machines (stragglers) on the completion time. We investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. This is motivated by recently available services in the cloud computing industry (e.g., EC2 Spot, Azure Batch) where low-priority virtual machines are offered at a fraction of the price of the on- demand instances but can be preempted on short notice. Our contributions are three-fold. We first introduce a new concept calledtransition wastethat quantifies the number of tasks existing machines must abandon or take over when a machine joins/leaves. We then develop an efficient method to minimize the transition waste for the cyclic task allocation scheme recently proposed in the literature (Yang et al. ISIT’19). Finally, we establish a novel solution based on finite geometry achievingzerotransition wastes given that the number of active machines varies within a fixed range.

Compute–forward is a coding technique that enables receiver(s) in a network to directly decode one or more linear combinations of the transmitted codewords. Initial efforts focused on Gaussian channels and derived achievable rate regions via nested lattice codes and single-user (lattice) decoding as well as sequential (lattice) decoding. Recently, these results have been generalized to discrete memoryless channels via nested linear codes and joint typicality coding, culminating in a simultaneous-decoding rate region for recovering one or more linear combinations from$K$users. Using a discretization approach, this paper translates this result into a simultaneous-decoding rate region for a wide class of continuous memoryless channels, including the important special case of Gaussian channels. Additionally, this paper derives a single, unified expression for both discrete and continuous rate regions via an algebraic generalization of Rényi’s information dimension.

Due to the weak security protection capabilities of the low-cost and low-complexity massive access of machine-type devices, massive machine-type communications (mMTC) networks are extremely vulnerable to the access jamming, which can affect the correctness of activity and data detection of legitimate devices and even leads to the paralysis of the mission-critical mMTC applications. This paper studies detection problem of the access jamming in the uplink of mMTC (AJ-UM), and we propose to exploit the characteristics of the joint low-rank factor and sparsity (JLFS) to detect the AJ-UM. Our detection method is motivated by the fact that the JLFS-based feature will be significantly impacted if the AJ-UM happens. We first extract the JLFS-based feature by solving a low-rank maximum likelihood factor analysis problem with sparsity constraint, and then perform the AJ-UM detection in a sequential manner. Moreover, the proposed JLFS-based method does not need to know the accurate prior information of the JLFS-based feature in the presence or absence of the AJ-UM, which can determine the AJ-UM exists as long as there is an abrupt change in the JLFS-based feature. Numerical results are finally presented to confirm the effectiveness of the proposed JLFS-based method.

As adoption of blockchain-based systems grows, more attention is being given to privacy of these systems. Early systems like BitCoin provided few privacy features. As a result, systems with strong privacy guarantees, including Monero, Zcash, and MimbleWimble have been developed. Compared to BitCoin, these cryptocurrencies are much less understood. In this paper, we focus on MimbleWimble, which uses the Dandelion++ protocol for private transaction relay and transaction aggregation to provide transaction content privacy. We find that in combination these two features make MimbleWimble susceptible to a new type of denial-of-service attacks. We design, prototype, and evaluate this attack on the Beam network using a private test network and a network simulator. We find that by controlling only 10% of the network nodes, the adversary can prevent over 45% of all transactions from ending up in the blockchain. We also discuss several potential approaches for mitigating this attack.

Unlike classical routing algorithms, quantum routing algorithms make use of entangled states—a type of resources that have a limited lifetime and need to be regenerated after consumption. In a nutshell, quantum routing algorithms have to use these resources efficiently, while optimizing some objectives such as the total waiting time. Current routing algorithms tend to keep a routing request waiting until all of the resources on its path are available. In this paper, we introduce a new way of managing entanglement resources in an opportunistic fashion: a request can move forward along its path as soon as possible (even if some resources on its path are not ready). We show that this opportunistic approach is fundamentally better than conventional approaches. In particular, our results indicate that this new approach achieves a 30-50% improvement in the average total waiting time and average link waiting time compared with several state-of-the-art routing algorithms. As a by-product of this work, we develop a new simulator for quantum routing, which can be used to evaluate various design choices under different scenarios.

Power-of-d-choices (Pod) is a popular load balancing strategy, which has received much attention from both academia and industry. However, much prior work on Pod has focused on uniform tasks without priorities. In reality, tasks may have different priorities according to their service sensitivity, pricing, or importance to guarantee the quality of service (QoS). In this work, we distinguish two types of priorities in Pod: scheduling and service priorities. We propose Pod-SSP, which is a Pod algorithm with Scheduling and Service Priorities. To better understand the impact of priorities on the performance of tasks, we consider two simple variants of Pod-SSP: Pod with SCheduling Priorities (Pod-SCP) and Pod with SErvice Priorities (Pod-SEP). Utilizing mean-field approximation, we systematically study the performance of these protocols in the large-system regime. Our theoretical and simulation results show that high-priority tasks can have a more than 3x better delay relative to a system running the original Pod algorithm, and meanwhile, low-priority tasks only slightly sacrifice their delay.

Exploiting short packets for communications is one of the key technologies for realizing emerging application scenarios such as massive machine type communications (mMTC) and ultra-reliable low-latency communications (uRLLC). In this paper, we investigate short-packet communications to provide both reliability and security guarantees simultaneously with an eavesdropper. In particular, an outage probability considering both reliability and secrecy is defined according to the characteristics of short-packet transmission, while the effective throughput in the sense of outage is established as the performance metric. Specifically, a general analytical framework is proposed to approximate the outage probability and effective throughput. Furthermore, closed-form expressions for these quantities are derived for the high signal-to-noise ratio (SNR) regime. Both effective throughput obtained via a general analytical framework and a high-SNR approximation are maximized under an outage-probability constraint by searching for the optimal blocklength. Numerical results verify the feasibility and accuracy of the proposed analytical framework, and illustrate the influence of the main system parameters on the blocklength and system performance under the outage-probability constraint.

Permissioned blockchains employ Byzantine fault-tolerant (BFT) state machine replication (SMR) to reach agreement on an ever-growing, linearly ordered log of transactions. A new paradigm, combined with decades of research in BFT SMR and blockchain (namely chained-BFT, or cBFT), has emerged for directly constructing blockchain protocols. Chained-BFT protocols have a unifying propose-vote scheme instead of multiple different voting phases with a set of voting and commit rules to guarantee safety and liveness. However, distinct voting and commit rules impose varying impacts on performance under different workloads, network conditions, and Byzantine attacks. Therefore, a fair comparison of the proposed protocols poses a challenge that has not yet been addressed by existing work. We fill this gap by studying a family of cBFT protocols with a two-pronged systematic approach. First, we present an evaluation and benchmarking framework, called Bamboo, for quick prototyping of cBFT protocols. To validate Bamboo, we introduce an analytic model using queuing theory which also offers a back-of-the-envelope guide for dissecting these protocols. We build multiple cBFT protocols using Bamboo and we are the first to fairly compare three cBFT representatives (i.e., HotStuff, two-chain HotStuff, and Streamlet). We evaluated these protocols under various parameters and scenarios, including two Byzantine attacks that have not been widely discussed in the literature. Our findings reveal interesting trade-offs (e.g., responsiveness vs. forking-resilience) between different cBFT protocols and their design choices, which provide developers and researchers with insights into the design and implementation of this protocol family.

HotStuff is a state-of-the-art Byzantine fault-tolerant consensus protocol. It can be pipelined to build large-scale blockchains. One of its variants called LibraBFT is adopted in Facebook's Libra blockchain. Although it is well known that pipelined HotStuff is secure against up to 1/3 of Byzantine nodes, its performance in terms of throughput and delay is still under-explored. In this paper, we develop a multi-metric evaluation framework to quantitatively analyze pipelined HotStuff's performance with respect to its chain growth rate, chain quality, and latency. We then propose several attack strategies and evaluate their effects on the performance of pipelined HotStuff. Our analysis shows that the chain growth rate (resp, chain quality) of pipelined HotStuff under our attacks can drop to as low as 4/9 (resp, 12/17) of that without attacks when 1/3 nodes are Byzantine. As another application, we use our framework to evaluate certain engineering optimizations adopted by LibraBFT. We find that these optimizations make the system more vulnerable to our attacks than the original pipelined HotStuff. Finally, we provide two countermeasures to thwart these attacks. We hope that our studies can shed light on the rigorous understanding of the state-of-the-art pipelined HotStuff protocol as well as its variants.

We present a novel unified framework of compute-forward achievable rate regions for simultaneous decoding of multiple linear codeword combinations. This framework covers a wide class of discrete and continuous-input channels, and computation over finite fields, integers, and reals. The resulting rate regions recover several well-known achievability results, and in some cases extend them. The framework is built upon a recently established achievable rate region based on linear codes and joint typicality decoding. The latter is extended from finite fields to computation over the integers and, via a discretization approach, to computation over the reals with integer coefficients and continuous inputs. Evaluating the latter with Gaussian distributions, we obtain a closed-form rate region which generalizes the classic compute-forward rates originally derived by means of lattice codes by Nazer and Gastpar.

Sidechains enable off-chain scaling by sending transactions in a private network rather than broadcasting them in the public blockchain (i.e., the mainchain) network. To this end, classic Byzantine fault-tolerant (BFT) consensus protocols such as PBFT seem an excellent fit to fuel sidechains for their permissioned settings and inherent robustness. However, designing a secure and efficient BFT-based sidechain protocol remains an open challenge.This paper presents Cumulus, a novel BFT-based sidechain framework for blockchains to achieve off-chain scaling without compromising any security and efficiency properties of both sides’ consensus protocols. Cumulus encompasses a novel cryptographic sortition algorithm called Proof-of-Wait to fairly select sidechain nodes to communicate with the mainchain in an efficient and decentralized manner. To further reduce the operational cost, Cumulus provides an optimistic checkpointing approach in which the mainchain will not verify checkpoints unless disputes happen. Meanwhile, end-users enjoy a two-step withdrawal protocol, ensuring that they can safely collect assets back to the mainchain without relying on the BFT committee. Our experiments show that Cumulus sidechains outperform ZK-Rollup, another promising sidechain construction, achieving one and two orders of magnitude improvement in throughput and latency while retaining comparable operational cost.

Synchronous Byzantine consensus has regained its popularity with the rise of permissioned blockchains due to its significantly better fault tolerance (up to minority faults) than its partially synchronous counterpart (less than one third). Dfinity Consensus is a state-of-the-art synchronous Byzantine consensus protocol. However, Dfinity is vulnerable to the withholding attack. For example, adversaries can strategically withhold blocks, resulting in an increase in latency and unbounded message complexity. Motivated by this observation, we present Dfinity++, which can effectively defend such an attack. The key idea behind Dfinity++ is simple. Since honest replicas would timely publish their blocks, one can detect delayed blocks and then trigger a fast switch to the next iteration, leading to better resource usage. Our results show that against a static/mildly adversary, Dfinity++ is able to reduce the latency (of committing a new block) by 10.7%, and at the same time enjoys a message complexity of $O\left(n^{2}\right)$.

The pilot scheme currently used in 5th generation (5G) cellular networks assigns the same set of orthogonal pilot signals to all cells. This results in inter-cell interference, also known as pilot contamination, which can significantly degrade performance, especially in massive multi-input multi-output (MIMO) systems. To mitigate this interference, we propose a novel Dual Pilot Scheme (DPS) that assigns a slightly modified set of nearly-orthogonal pilot signals. DPS is a general scheme that can be implemented in any wireless communication system, including 5G and beyond. We demonstrate the integration of DPS in a massive MIMO system in both microscopic and macroscopic levels and analytically prove that DPS enables more accurate estimates of the channel state information in the minimum mean-squared error sense, under the independent identically distributed (i.i.d.) and the correlated Rayleigh fading wireless communication channel models. We further validate and demonstrate the advantages of DPS over various channel models of massive MIMO 5G technology by extensive simulations.

In this paper, we study millimeter wave (mmWave) communications of an uplink cellular vehicle-to-everything (C-V2X) network consisting of vehicles, pedestrians, road side units (RSUs), and cellular base stations (BSs). We propose an association scheme that a vehicle delivers messages to either the V2X nodes, including vehicles, pedestrians, and RSUs, or the BSs, based on the distance and the bias factor. Subsequently, we provide a tractable analytical framework to comprehensively assess the reliability performance of the considered uplink transmission, in terms of success probability. By leveraging the stochastic geometry theory, we model the locations of vehicles, pedestrians, and RSUs as independent cox process and model the locations of BSs as a Poisson point process (PPP), and derive new expressions for the association probability, the success probability of different associating types, and the overall success probability of the C-V2X network. Numerical results are presented to validate the theoretical analyses and provide interesting insights into how the success probability is influenced by various parameters, including the signal-to-interference-plus-noise ratio (SINR) threshold, the densities of V2X nodes and BSs, the blockage density, and the bias factor.

Motivated by recently available services in the cloud computing industry, e.g., EC2 Spot or Azure Batch, where spare/low-priority virtual machines are offered at a fraction of the price of the on-demand instances but can be preempted on short notice, we investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. Our contributions are two-fold: We first propose an efficient method to minimize the transition waste, a newly introduced concept quantifying the total number of tasks that existing machines have to abandon or take on anew when a machine joins or leaves, for the cyclic elastic task allocation scheme recently proposed in the literature (Yang et al. ISIT'19). We then proceed to generalize such a scheme and introduce new task allocation schemes based on finite geometry that achieve zero transition wastes as long as the number of active machines varies within a fixed range. The proposed solutions can be applied on top of existing coded computing schemes tolerating stragglers.

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations of codewords can sometimes be decoded more efficiently than codewords themselves. The present work further develops this framework by studying the simultaneous decoding of multiple messages. Specifically, consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with “single-user” or sequential decoding can yield better achievable rates. For instance, the compute-forward problem examines the scenario of recovering L ≤ K linear combinations of transmitted codewords over a K-user multiple-access channel (MAC), and it is well established that linear codebooks can yield higher rates. This paper develops bounds for simultaneous joint typicality decoding used in conjunction with nested linear codebooks, and applies them to obtain a larger achievable region for compute-forward over a K-user discrete memoryless MAC. The key technical challenge is that competing codeword tuples that are linearly dependent on the true codeword tuple introduce statistical dependencies, which requires careful partitioning of the associated error events.

As the second largest cryptocurrency by market capitalization and today's biggest decentralized platform that runs smart contracts, Ethereum has received much attention from both academia and industry. Nevertheless, there exist very few studies about the security of its mining strategies, especially from the selfish mining perspective. In this paper, we fill this research gap by analyzing selfish mining in Ethereum and understanding its potential threat. First, we introduce a 2-dimensional Markov process to model the behavior of a selfish mining strategy inspired by a Bitcoin mining strategy proposed by Eyal and Sirer. Second, we derive the stationary distribution of our Markov model and compute long-term average mining rewards. This allows us to determine the threshold of computational power which makes selfish mining profitable in Ethereum. We find that this threshold is lower than that in Bitcoin mining (which is 25% as discovered by Eyal and Sirer), suggesting that Ethereum is more vulnerable to selfish mining than Bitcoin.

Consider the important special case of the K-user distributed source coding problem where the decoder only wishes to recover one or more linear combinations of the sources. The work of Körner and Marton demonstrated that, in some cases, the optimal rate region is attained by random linear codes, and strictly improves upon the best-known achievable rate region established via random i.i.d. codes. Recent efforts have sought to develop a framework for characterizing the achievable rate region for nested linear codes via joint typicality encoding and decoding. Here, we make further progress along this direction by proposing an achievable rate region for simultaneous joint typicality decoding of nested linear codes. Our approach generalizes the results of Körner and Marton to computing an arbitrary number of linear combinations and to the lossy computation setting.

Compute-and-forward (C&F) recently finds new applications in random-access networks focusing on the single access point (AP) scenario. In this paper, we extend the use of C&F from the single AP scenario to the multi-AP scenario. To achieve this, we identify two major challenges and propose two novel solutions. First, we introduce an AP cooperation problem and develop an efficient distributed algorithm. Second, we introduce a joint channel estimation and active user recovery problem and propose a solution based on spare recovery techniques. In addition, we provide accurate throughput and delay expressions for C&F-based carrier-sense multiple access (CSMA) protocols. These expressions, together with our trace-driven simulations, demonstrate the significant advantages of C&F-based CSMA over conventional CSMA in the multi-AP scenario.

This paper presents a joint typicality framework for encoding and decoding nested linear codes in multi-user networks. This framework provides a new perspective on compute-forward within the context of discrete memoryless networks. In particular, it establishes an achievable rate region for computing a linear combination over a discrete memoryless multiple-access channel (MAC). When specialized to the Gaussian MAC, this rate region recovers and improves upon the lattice-based compute-forward rate region of Nazer and Gastpar, thus providing a unified approach for discrete memoryless and Gaussian networks. Furthermore, our framework provides some valuable insights on establishing the optimal decoding rate region for compute-forward by considering joint decoders, progressing beyond most previous works that consider successive cancellation decoding. Specifically, this paper establishes an achievable rate region for simultaneously decoding two linear combinations of nested linear codewords from K senders.

Recent work has proposed the integer-forcing (IF) linear receiver architecture as a promising alternative to the joint maximum likelihood (ML) receiver. It has been proven that the IF linear receiver can operate very close to the (optimal) performance of the joint ML receiver, but with essentially the same implementation complexity as a zero-forcing (ZF) linear receiver. In this paper, we take the first steps towards a complete software-defined radio (SDR) implementation of the IF linear receiver. Using the Wireless Open-Access Radio Platform (WARP) and IEEE 802.11 protocols, we develop an OFDM-based experimental framework to evaluate the performance of IF linear receivers in realistic indoor settings, and compare it to the performance of ZF and joint ML receivers. Our framework includes a channel estimation protocol and algorithm for selecting the best integer matrix for approximating the channel matrix. We have performed indoor experiments for a 2 × 2 MIMO network, which demonstrate that the symbol error rate (SER) of the IF linear receiver indeed outperforms the ZF linear receiver and can operate close to the joint ML receiver. We also argue, via simulations, that IF continues to outperform conventional linear receivers, even in the presence of significant channel estimation errors.

Recent work has employed joint typicality encoding and decoding of nested linear code ensembles to generalize the compute-forward strategy to discrete memoryless multiple-access channels (MACs). An appealing feature of these nested linear code ensembles is that the coding strategies and error probability bounds are conceptually similar to classical techniques for random i.i.d. code ensembles. In this paper, we consider the problem of recovering K linearly independent combinations over a K-user MAC, i.e., recovering the messages in their entirety via nested linear codes. While the MAC rate region is well-understood for random i.i.d. code ensembles, new techniques are needed to handle the statistical dependencies between competing codeword K-tuples that occur in nested linear code ensembles.

Nested lattice codes have played an important role in network information theory. However, their achievability proofs are often involved, even for the case of the additive white Gaussian noise (AWGN) channel. In sharp contrast, their finite-field counterparts, nested linear codes, enjoy much simpler achievability proofs. In this paper, we present a simple and direct proof that nested lattice codes achieve the AWGN channel capacity. In particular, we make use of an intriguing connection between nested lattice codes and nested linear codes, which allows us to keep the proof as simple as that for nested linear codes.

The uplink transmission in a Massive MIMO system is studied. Pilot contamination during the uplink training is the main inherent limitation that degrades the performance of Massive MIMO. Current approaches are using the same pilot sequences for every cell, leading to the so-called inter-cell interference. In this paper, a novel method that employs dual pilot sequences is proposed where different cells are assigned with different pilot sequences (called them cells' IDs). In particular, each cell has the same set of orthogonal pilot sequences together with a unique pilot sequence (cell's ID). This dual structure mitigates pilot contamination, achieving better channel estimation at various signal-to-noise ratios.

The problem of carrier sense multiple access (CSMA) with multi-packet reception (MPR) is studied. Most prior work has focused on the homogeneous case, where all the mobile users are assumed to have identical packet arrival rates and transmission probabilities. The inhomogeneous case remains largely open in the literature. In this paper, we make a first step toward this open problem by deriving throughput and delay expressions for inhomogeneous CSMA, with a particular focus on a family of MPR models. This family of MPR models, which allows us to overcome several challenges associated with conventional analysis, is general enough to include a number of interesting MPR techniques-such as successive interference cancellation, compute-and-forward (C&F), and successive C&F (SCF)-as special cases. Based on these throughput and delay expressions, we provide theoretical guidelines for the network design to meet quality-of-service requirements and to achieve global stability; we also evaluate the performances of various MPR techniques, highlighting the clear advantages offered by SCF.

In this paper, we introduce a unified framework for studying various cloud traffic management problems, ranging from geographical load balancing to backbone traffic engineering. We first abstract these real-world problems as a multi-facility resource allocation problem, and then present two distributed optimization algorithms by exploiting the special structure of the problem. Our algorithms are inspired by Alternating Direction Method of Multipliers (ADMM), enjoying a number of unique features. Compared to dual decomposition, they converge with non-strictly convex objective functions; compared to other ADMM-type algorithms, they not only achieve faster convergence under weaker assumptions, but also have lower computational complexity and lower message-passing overhead. The simulation results not only confirm these desirable features of our algorithms, but also highlight several additional advantages, such as scalability and fault-tolerance.

Compute-and-forward (C&F) is a promising new approach to interference management, enjoying several advantages over other information-theoretic schemes. C&F usually requires channel state information (CSI) at the receivers so that an “optimal” scaling factor can be computed for the purposes of decoding. In this paper, a blind C&F scheme-i.e., one not requiring CSI-is developed. Rather than attempting to compute the optimal scaling factor, this new scheme seeks one or more “good” scalars, i.e., scalars that allow correct decoding despite possibly being suboptimal. The region of all such good scalars is characterized. To find a good scalar, a computationally efficient scheme is proposed which involves error-detection, a hierarchically organized list, as well as a use of the smoothing lemma from lattice theory. Simulation results show that our blind C&F scheme achieves-for a class of nested lattice codes-the same throughput as its CSI-enabled counterpart at the expense of, approximately, a two-fold increase in computational complexity in the high-throughput region. Moreover, our blind C&F scheme can be applied to multisource multirelay networks with a good performance/complexity tradeoff.

The benefit of applying compute-and-forward (C&F) to slotted ALOHA (S-ALOHA) systems is studied. A Markov chain model is introduced, and an approximate stability region is given. It is shown that the approximate region is asymptotically exact as the number of users tends to infinity. It is also shown that the approximate region is very accurate even for systems with a small number of users. Further, based on the approximate region, simple expressions for the throughput and delay performance of S-ALOHA with C&F are derived, demonstrating the significant advantages offered by C&F.

Consider a cellular network composed of several base stations with overlapping coverage areas. Conventional scheduling algorithms ensure that each base station hears only a single user over each orthogonal sub-channel, i.e., collisions are avoided. Recent work on compute-and-forward has demonstrated that it is possible for a receiver to decode a linear combination of interfering codewords. We examine how the adoption of the compute-and-forward technique affects the scheduling problem for cellular networks. Specifically, instead of avoiding collisions, the base stations can schedule collisions to obtain a set of linear combinations that can be solved for the original messages. For the special case of two base stations, we propose a simple scheduling algorithm that finds the minimal number of sub-channels needed for each user to successfully communicate one packet. For the general case, we formulate an integer program that can be solved using dynamic programming with pseudo-polynomial complexity with respect to the number of users.

Conventional scheduling algorithms assign users to orthogonal sub-channels in order to avoid collisions. However, recent physical-layer advances, such as the compute-and-forward technique, have demonstrated that it is possible to recover a linear combination of packets when a collision occurs. Recently, we proposed a collision scheduling algorithm that exploits this phenomenon to attain higher throughputs. Here, we argue that the complexity of this algorithm can be significantly reduced in the important special case where each cell only overlaps with a constant number of neighboring cells.

Lately, for geo-distributed data centers, a workload management approach that routes user requests to locations with cheaper and cleaner electricity has been developed to reduce energy consumption and cost. We consider two key aspects that have not been explored in this approach. First, through empirical studies, we find that the energy efficiency of cooling systems depends critically on the ambient temperature, which exhibits significant geographical diversity. Temperature diversity can be used to reduce the cooling energy overhead. Second, energy consumption comes from not only interactive workloads driven by user requests, but also delay tolerant batch workloads that run at the back-end. The elastic nature of batch workloads can be exploited to further reduce the energy cost. In this paper, we propose to make workload management temperature aware. We formulate the problem as a joint optimization of request routing for interactive workloads and capacity allocation for batch workloads. We develop a distributed algorithm based on an m-block alternating direction method of multipliers (ADMM) algorithm that extends the classical two-block algorithm. We prove the convergence and rate of convergence results under general assumptions. Through trace-driven simulations, we find that our approach consistently provides 15-20 percent cooling energy reduction, and 5-20 percent overall cost reduction over existing methods.

Middleboxes are widely deployed in today's networks. They apply a variety of complex network functions to transform, filter, and optimize incoming traffic based on the payload of packets. These functions require the support of multiple types of resources, such as CPU and link bandwidth, for processing incoming packets. Hence, a multi-resource packet scheduling algorithm is needed to allow flows to share these resources fairly and efficiently. However, unlike traditional fair queueing where bandwidth is the only concern, we show in this paper that fairness and efficiency are conflicting objectives that cannot be achieved simultaneously in the presence of multiple resources. Ideally, a scheduling algorithm should allow network operators to flexibly specify their fairness and efficiency requirements, so as to meet the Quality of Service demands while keeping the system at a high utilization level. Yet, existing multi-resource scheduling algorithms focus on fairness only, and may lead to poor resource utilization. In this paper, we propose a new scheduling algorithm to achieve a flexible tradeoff between fairness and efficiency for packet processing, consuming both CPU and link bandwidth. Experimental results based on both real-world implementation and trace-driven simulation suggest that trading off a modest level of fairness can potentially improve the efficiency to the point where the system capacity is almost saturated.

Though network coding is traditionally performed over finite fields, recent work on nested-lattice-based network coding suggests that, by allowing network coding over certain finite rings, more efficient physical-layer network coding schemes can be constructed. This paper considers the problem of communication over a finite-ring matrix channel Y = AX + BE, where X is the channel input, Y is the channel output, E is random error, and A and B are random transfer matrices. Tight capacity results are obtained and simple polynomial-complexity capacity-achieving coding schemes are provided under the assumption that A is uniform over all full-rank matrices and BE is uniform over all rank-t matrices, extending the work of Silva, Kschischang, and Kötter (2010), who handled the case of finite fields. This extension is based on several new results, which may be of independent interest, that generalize concepts and methods from matrices over finite fields to matrices over finite chain rings.

Though network coding is traditionally performed over finite fields, recent work on nested-lattice-based network coding suggests that, by allowing network coding over finite rings, more efficient physical-layer network coding schemes can be constructed. This paper considers the problem of communication over a finite-chain-ring matrix channel Y = AX + BZ, where X is the channel input, Y is the channel output, Z is random noise, and A and B are random transfer matrices. Tight capacity results are obtained and simple polynomial-complexity capacity-achieving coding schemes are provided under certain distributions of A, B, and Z, extending the work of Silva, Kschischang and Kötter (2010), who handled the case of finite fields. This extension is based on several new results that generalize concepts and methods from matrices over finite fields to matrices over finite chain rings.

Datacenters consume an enormous amount of energy with significant financial and environmental costs. For geo-distributed datacenters, a workload management approach that routes user requests to locations with cheaper and cleaner electricity has been shown to be promising lately. We consider two key aspects that have not been explored in this approach. First, through empirical studies, we find that the energy efficiency of the cooling system depends directly on the ambient temperature, which exhibits a significant degree of geographical diversity. Temperature diversity can be used by workload management to reduce the overall cooling energy overhead. Second, energy consumption comes from not only interactive workloads driven by user requests, but also delay tolerant batch workloads that run at the back-end. The elastic nature of batch workloads can be exploited to further reduce the energy cost. In this work, we propose to make workload management for geo-distributed datacenters temperature aware. We formulate the problem as a joint optimization of request routing for interactive workloads and capacity allocation for batch workloads. We develop a distributed algorithm based on an m-block alternating direction method of multipliers (ADMM) algorithm that extends the classical 2-block algorithm. We prove the convergence and rate of convergence results under general assumptions. Trace-driven simulations demonstrate that our approach is able to provide 5%--20% overall cost savings for geo-distributed datacenters.

The problem of designing physical-layer network coding (PNC) schemes via nested lattices is considered. Building on the compute-and-forward (C&F) relaying strategy of Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, an algebraic approach is taken to show its potential in practical, nonasymptotic, settings. A general framework is developed for studying nested-lattice-based PNC schemes-called lattice network coding (LNC) schemes for short-by making a direct connection between C&F and module theory. In particular, a generic LNC scheme is presented that makes no assumptions on the underlying nested lattice code. C&F is reinterpreted in this framework, and several generalized constructions of LNC schemes are given. The generic LNC scheme naturally leads to a linear network coding channel over modules, based on which noncoherent network coding can be achieved. Next, performance/complexity tradeoffs of LNC schemes are studied, with a particular focus on hypercube-shaped LNC schemes. The error probability of this class of LNC schemes is largely determined by the minimum intercoset distances of the underlying nested lattice code. Several illustrative hypercube-shaped LNC schemes are designed based on Constructions A and D, showing that nominal coding gains of 3 to 7.5 dB can be obtained with reasonable decoding complexity. Finally, the possibility of decoding multiple linear combinations is considered and related to the shortest independent vectors problem. A notion of dominant solutions is developed together with a suitable lattice-reduction-based algorithm.

An indoor tracking and navigation system based on measurements of received signal strength (RSS) in wireless local area network (WLAN) is proposed. In the system, the location determination problem is solved by first applying a proximity constraint to limit the distance between a coarse estimate of the current position and a previous estimate. Then, a Compressive Sensing-based (CS--based) positioning scheme, proposed in our previous work , , is applied to obtain a refined position estimate. The refined estimate is used with a map-adaptive Kalman filter, which assumes a linear motion between intersections on a map that describes the user's path, to obtain a more robust position estimate. Experimental results with the system that is implemented on a PDA with limited resources (HP iPAQ hx2750 PDA) show that the proposed tracking system outperforms the widely used traditional positioning and tracking systems. Meanwhile, the tracking system leads to 12.6 percent reduction in the mean position error compared to the CS-based stationary positioning system when three APs are used. A navigation module that is integrated with the tracking system provides users with instructions to guide them to predefined destinations. Thirty visually impaired subjects from the Canadian National Institute for the Blind (CNIB) were invited to further evaluate the performance of the navigation system. Testing results suggest that the proposed system can be used to guide visually impaired subjects to their desired destinations.

Current-generation cloud computing is offered with usage-based pricing, with no bandwidth capacity guarantees, which is however unappealing to bandwidth-intensive applications such as video-on-demand (VoD). We consider a new type of service where VoD providers, such as Netflix and Hulu, make reservations for bandwidth guarantees from the cloud at negotiable prices to support continuous media streaming. We argue that it is beneficial to multiplex such bandwidth reservations in the market using a profit-making broker while controlling the performance risks. We ask the question-in such a market, how much should each VoD provider pay for bandwidth reservation? We prove that the market has a unique Nash equilibrium where the bandwidth reservation price for a VoD provider critically depends on its demand correlation to the market. Real-world traces verify that our theory can significantly lower the market price for cloud bandwidth reservation.

Compute-and-forward (C&F) relaying usually requires channel state information (CSI) at the receivers so that an “optimal” scale factor can be computed for the purposes of decoding. In this paper, a blind C&F scheme - i.e., one not requiring CSI - is developed. Rather than attempting to compute the optimal scale factor, this new scheme seeks one (or more) “good” scalars, i.e., scalars which allow correct decoding despite possibly being sub-optimal. The region of all such good scalars is characterized. To find a good scalar, a computationally efficient scheme, involving error-detection and a hierarchically organized list, is proposed. Simulation results show that this blind C&F scheme achieves - for a class of lattices admitting an efficient trellis decoder - the same throughput as its CSI-enabled counterpart, at the expense of, approximately, a ten-fold increase in computational complexity in the high-throughput region.

In a public cloud, bandwidth is traditionally priced in a pay-as-you-go model. Reflecting the recent trend of augmenting cloud computing with bandwidth guarantees, we consider a novel model of cloud bandwidth allocation and pricing when explicit bandwidth reservation is enabled. We argue that a tenant's utility depends not only on its bandwidth usage, but more importantly on the portion of its demand that is satisfied with a performance guarantee. Our objective is to determine the optimal policy for pricing cloud bandwidth reservations, in order to maximize social welfare, i.e., the sum of the expected profits that can be made by all tenants and the cloud provider, even with the presence of demand uncertainty. The problem turns out to be a large-scale network optimization problem with a coupled objective function. We propose two new distributed solutions --- based on chaotic equation updates and cutting-plane methods --- that prove to be more efficient than existing solutions based on consistency pricing and subgradient methods. In addition, we address the practical challenge of forecasting demand statistics, required by our optimization problem as input. We propose a factor model for near-future demand prediction, and test it on a real-world video workload dataset. All included, we have designed a fully computerized trading environment for cloud bandwidth reservations, which operates effectively at a fine granularity of as small as ten minutes in our trace-driven simulations.

The recent growing interest for indoor Location-Based Services (LBSs) has created a need for more accurate and real-time indoor positioning solutions. The sparse nature of location finding makes the theory of Compressive Sensing (CS) desirable for accurate indoor positioning using Received Signal Strength (RSS) from Wireless Local Area Network (WLAN) Access Points (APs). We propose an accurate RSS-based indoor positioning system using the theory of compressive sensing, which is a method to recover sparse signals from a small number of noisy measurements by solving an `1-minimization problem. Our location estimator consists of a coarse localizer, where the RSS is compared to a number of clusters to detect in which cluster the node is located, followed by a fine localization step, using the theory of compressive sensing, to further refine the location estimation. We have investigated different coarse localization schemes and AP selection approaches to increase the accuracy. We also show that the CS theory can be used to reconstruct the RSS radio map from measurements at only a small number of fingerprints, reducing the number of measurements significantly. We have implemented the proposed system on a WiFi-integrated mobile device and have evaluated the performance. Experimental results indicate that the proposed system leads to substantial improvement on localization accuracy and complexity over the widely used traditional fingerprinting methods.

The construction of lattice network coding schemes through signal codes is revisited. First, it is shown that the nominal coding gain of signal codes can be carried over from AWGN channels to lattice network coding. This demonstrates the potential of using signal codes in lattice network coding. However, in order to achieve the promised performance gain, all the side information related to shaping should be transmitted to the receiver. Second, the problem of delivering the side information to the receiver is considered. In particular, a generic scheme is proposed which can be optimized by solving a lattice design problem. Finally, two solutions to the lattice design problem are presented and the simulation results suggest that-with a reasonable overhead-the promised performance gain can be achieved by using our proposed scheme.

The low rank feature of location estimation in Wireless Sensor Networks (WSNs) makes it feasible to use nuclear norm minimization as an accurate and fast solution for low-dimensional embedding problems. In this paper, a novel localization algorithm for WSNs is proposed by using nuclear norm for rank minimization. We formulate the location finding problem from only a small fraction of random entries of Euclidean Distance Matrix (EDM) as a low-rank matrix recovery problem, subject to a set of linear equality constraints. We show that a measurement matrix using orthogonal projection obeys the RIP and thus, supports a sufficient condition for the recovery of the low-rank matrix with overwhelming probability. For simplicity, Singular Value Thresholding (SVT) algorithm, a standard convex optimization approach, is used for the nuclear norm minimization. Simulation results demonstrate that in a 100 m × 100 m area, for a small scale network with 100 nodes, only 20% of measurements is needed to achieve a 0.5 m localization error, while 3% needed to achieve a 0.05 m error for a comparatively large scale network with 1000 nodes.

The sparse nature of location finding problem makes the theory of compressive sensing desirable for indoor positioning in Wireless Local Area Networks (WLANs). In this paper, we address the received signal strength (RSS)-based localization problem in WLANs using the theory of compressive sensing (CS), which offers accurate recovery of sparse signals from a small number of measurements by solving an ¿1-minimization problem. A pre-processing procedure of orthogonalization is used to induce incoherence needed in the CS theory. In order to mitigate the effects of RSS variations due to channel impediments, the proposed positioning system consists of two steps: coarse localization by exploiting affinity propagation, and fine localization by the CS theory. In the fine localization stage, access point selection problem is studied to further increase the accuracy. We implement the positioning system on a WiFi-integrated mobile device (HP iPAQ hx4700 with Windows Mobile 2003 Pocket PC) to evaluate the performance. Experimental results indicate that the proposed system leads to substantial improvements on localization accuracy and complexity over the widely used traditional fingerprinting methods.

The problem of designing new physical-layer network coding (PNC) schemes via lattice partitions is considered. Building on a recent work by Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, we take an algebraic approach to show its potential in non-asymptotic settings. We first relate Nazer-Gastpar's approach to the fundamental theorem of finitely generated modules over a principle ideal domain. Based on this connection, we generalize their code construction and simplify their encoding and decoding methods. This not only provides a transparent understanding of their approach, but more importantly, it opens up the opportunity to design efficient and practical PNC schemes. Finally, we apply our framework for PNC to a Gaussian relay network and demonstrate its advantage over conventional PNC schemes.

In this paper, a novel multiple target localization approach is proposed by exploiting the compressive sensing theory, which indicates that sparse or compressible signals can be recovered from far fewer samples than that needed by the Nyquist sampling theorem. We formulate the multiple target locations as a sparse matrix in the discrete spatial domain. The proposed algorithm uses the received signal strengths (RSSs) to find the location of targets. Instead of recording all RSSs over the spatial grid to construct a radio map from targets, far fewer numbers of RSS measurements are collected, and a data pre-processing procedure is introduced. Then, the target locations can be recovered from these noisy measurements, only through an ¿1-minimization program. The proposed approach reduces the number of measurements in a logarithmic sense, while achieves a high level of localization accuracy. Analytical studies and simulations are provided to show the performance of the proposed approach on localization accuracy.

Pull-based mesh streaming protocols have recently received much research attention, with successful commercial systems showing their viability in the Internet. Despite the remarkable popularity in real-world systems, the fundamental properties and limitations of pull-based protocols are not yet well understood from a theoretical perspective, as there exists no prior work that studies the performance gap between the fundamental limits and the actual performance. In this paper, we develop a unified framework based on trellis graph techniques to mathematically analyze and understand the performance of pull-based mesh streaming protocols, with a particular focus on such a performance gap. We show that there exists a significant performance gap that separates the actual and optimal performance of pull-based mesh protocols. Moreover, periodic buffer map exchanges account for most of this performance gap. Our analytical characterization of the performance gap brings us not only a better understanding of several fundamental tradeoffs in pull-based mesh protocols, but also important insights on the design of practical streaming systems that can achieve high streaming rates and short initial buffering delays.

In this paper, a novel compressive sensing for manifold learning protocol (CSML) is proposed for localization in wireless sensor networks (WSNs). Intersensor communication costs are reduced significantly by applying the theory of compressive sensing, which indicates that sparse signals can be recovered from far fewer samples than that needed by the Nyquist sampling theorem. We represent the pair-wise distance measurement as a sparse matrix. Instead of sending full pair-wise measurement data to a central node, each sensor transmits only a small number of compressive measurements. And the full pair-wise distance matrix can be well reconstructed from these noisy compressive measurements in the central node, only through an ¿1-minimization algorithm. The proposed method reduces the overall communication bandwidth requirement per sensor such that it increases logarithmically with the number of sensors and linearly with the number of neighbors, while achieves high localization accuracy. CSML is especially suitable for manifold learning based localization algorithms. Simulation results demonstrate the performance of the proposed protocol on both the localization accuracy and the communication cost reduction.

Live peer-to-peer (P2P) streaming has recently received much research attention, with successful commercial systems showing its viability in the Internet. Nevertheless, existing analytical studies of P2P streaming systems have failed to mathematically investigate and understand their critical properties, especially with a large scale and under extreme dynamics such as a flash crowd scenario. Even more importantly, there exists no prior analytical work that focuses on an entirely new way of designing streaming protocols, with the help of network coding. In this paper, we seek to show an in-depth analytical understanding of fundamental properties of P2P streaming systems, with a particular spotlight on the benefits of network coding. We show that, if network coding is used according to certain design principles, provably good performance can be guaranteed, with respect to high playback qualities, short initial buffering delays, resilience to peer dynamics, as well as minimal bandwidth costs on dedicated streaming servers. Our results are obtained with mathematical rigor, but without sacrificing realistic assumptions of system scale, peer dynamics, and upload capacities. For further insights, streaming systems using network coding are compared with traditional pull-based streaming in large-scale simulations, with a focus on fundamentals, rather than protocol details. The scale of our simulations throughout this paper exceeds 200,000 peers at times, which is in sharp contrast with existing empirical studies, typically with a few hundred peers involved.