The openness of wireless networks enables flexible connections on devices, but also arises the security and privacy concerns on adversarial eavesdropping. By concealing the transmissions from eavesdropper, covert communication preserves the privacy of communications and has become a significant research topic. Whereas, existing works primarily focus on the covertness of communication links, neglecting the protection for the critical leader nodes response for information aggregation and decision making in information systems. To bridge this gap, we introduce a novel conceptcovert leader, whose identity remains concealed from all other nodes while performing leadership functions. This design inherently mitigates targeted attacks (e.g., eavesdropping, jamming, DoS) against leaders, enhancing both privacy and robustness of wireless network. Then, a distributed randomizedK-Covert Leader Election (KCLE) algorithm is designed, in whichKis a hyperparameter to depict the covertness of leader election and can be adjusted when KCLE algorithm is implemented in reality. Unlike cryptographic solutions, KCLE leverages physical-layer signal properties to elect a leader from at leastKcandidates with balanced energy-time tradeoffs, ensuring no leader identity leakage occurs during election. The algorithm operates without complex encryption, making it suitable for resource-constrained Internet-of-Things and ad hoc networks. Theoretical analysis and simulation results demonstrate KCLE’s correctness, covertness guarantees, and operational efficiency under SINR interference models.

The decentralized nature of federated learning (FL) makes it difficult to verify the trustworthiness of participating clients, creating an opportunity for backdoor attacks. This paper addresses a general backdoor-resilient decentralized FL problem without any prior knowledge of the type of backdoor attacks or information about malicious clients. After an in-depth investigation of how backdoor attacks are conducted in FL, we introduce a multi-armed bandit-based knowledge distillation approach to help benign clients learn useful knowledge from other clients while rejecting potential backdoors hidden in shared updates. Unlike most previous works that rely on identifying and removing malicious updates—an approach limited to scenarios with fewer than 50% attackers—our knowledge distillation technique enables benign clients to reject backdoored knowledge while preserving useful information, maintaining effective defense even when malicious clients exceed 50% of the population. Additionally, to handle the various updates from clients with Non-IID dataset, a multi-armed bandit scheme is designed for each benign client to select the most appropriate teachers for knowledge distillation, resulting in high accuracy and fast convergence. Extensive experiments demonstrate that our multi-armed bandit-based knowledge distillation approach achieves high accuracy and general backdoor resilience. Comparisons with previous works show that our approach can reduce the attack success rate by 14.71%∼96.78% on average.

In this work, we study to release the potential of massive heterogeneous weak computing power to collaboratively train large-scale models on dispersed datasets. In order to improve both efficiency and accuracy in resource-adaptive collaborative learning, we take the first step to consider the unstructured pruning, varying submodel architectures, knowledge loss, and straggler challenges simultaneously. We propose a novel semiasynchronous collaborative training framework, namely Co-S2P, with data distribution-aware structured pruning and cross-block knowledge transfer mechanism to address the above concerns. Furthermore, we provide theoretical proof that Co-S2P can achieve asymptotic optimal convergence rate of O(1/√ N∗EQ). Finally, we conduct extensive experiments on two types of tasks with a real-world hardware testbed including diverse IoT devices. The experimental results demonstrate that Co-S2P improves accuracy by up to 8.8% and resource utilization by up to 1.2× compared to state-of-the-art methods, while reducing memory consumption by approximately 22% and training time by about 24% on all resource-limited devices.

As a combination of digital twin and edge computing, the digital twin edge networks (DITENs) have gained significant interest due to their bridging roles between physical edge networks and digital systems. The Device-to-Device (D2D) communication acts as an ongoing transmission paradigm for DITENs since it facilitates interoperability between nearby wireless entities and enhances the spectrum utilization and overall throughput via direct link. However, most existing works on the D2D communication are related to the centralized ones, and consider the mobility and interference management separately, which cannot be used for the dynamic scenarios in DITENs. In this paper, we consider the D2D communication problem in dynamic DITENs in the context of the SINR model, and propose a dynamicity-tolerant D2D communication algorithm in a distributed manner. Using an oblivious transmission strategy, our algorithm can complete the D2D communication among$n$entities within$O(\log n)$time steps despite the various dynamic factors, which achieves asymptotically optimal time complexity. It is asserted that the D2D communication algorithm is asymptotically optimal, given that the lower bound for successful message dissemination is$\Omega (\log n)$. Rigorous theoretical analyses and empirical results are conducted to show the correctness and efficiency of our proposed algorithm.

This paper studies an efficient federated learning (FL) problem involving multiple edge-based clients with heterogeneous constrained resources. Compared with numerous training parameters, the computing and communication resources of clients in edge scenarios are usually insufficient for fast local training and real-time knowledge sharing. Besides, training on clients with heterogeneous resources may result in the straggler problem, which delays the convergence of FL. To address these issues, we proposeFed-RAA: aResource-AdaptiveAsynchronousFederated learning algorithm. Different from vanilla FL methods, where all parameters are trained by each participating client regardless of resource diversity, Fed-RAA adaptively allocates submodels of the global model to clients based on their computing and communication capabilities. Each client then individually trains its assigned submodel and asynchronously uploads the updated result. Theoretical analysis confirms the convergence of our approach. Additionally, an online greedy-based algorithm is designed for asynchronous submodel assignment in Fed-RAA, improving the convergence of Fed-RAA by optimal minimization on the training delay bound of submodels. Compared to state-of-the-art methods, our Fed-RAA algorithm reduces the time required to achieve the target accuracy by an average of$ 30.89\%$, demonstrating its superior efficiency on heterogeneous constrained computing and communication resources. To the best of our knowledge, this paper is the first resource-adaptive asynchronous method for submodel-based FL with guaranteed theoretical convergence.

The growing resource demands of large-scale transformer models pose significant challenges for resource-constrained users, particularly in distributed environments. To address this issue, we propose a federated learning framework called Fed-Grow, which enables multiple participants to collaboratively learn a lightweight scaling operation that transfers knowledge from pretrained small models to a large transformer model. In Fed-Grow, we introduce the Dual-LiGO (Dual Linear Growth Operator) architecture, consisting of Local-LiGO and Global-LiGO components. Local-LiGO addresses model heterogeneity by adapting each participant's pre-trained model to a common intermediate form, while Global-LiGO facilitates knowledge sharing across participants without sharing local models or raw data, ensuring privacy preservation. This federated approach offers a scalable solution for growing large transformers in a distributed manner, where only the Global-LiGO is shared, significantly reducing communication overhead while maintaining comparable model performance under the same communication constraints. Experimental results demonstrate that Fed-Grow outperforms state-of-the-art methods in terms of accuracy and precision, while reducing the number of trainable parameters by 59.25% and communication costs by 73.01%. These improvements allow for higher efficiency in training large models in distributed environments, without sacrificing performance. To the best of our knowledge, Fed-Grow is the first method that enables cooperative transformer scaling in a distributed setting, making it a practical solution for resource-constrained users.

Meta computing, as an innovative computing paradigm, aims to transform the Internet into a vast and distributed computing resource pool. This paradigm holds significant promise for the Industrial Internet of Things (IIoT), offering efficient, fault-tolerant, and personalized services while ensuring strong security and privacy. Nowadays, content delivery networks (CDNs) are integral to this vision, providing critical network support by reducing latency, alleviating network congestion, and enhancing service quality. Accurate prediction of CDN cache group performance, which involves heterogeneous edge servers handling diverse workloads, is essential for optimal resource utilization, dynamic load balancing, and efficient traffic management in IIoT. This article addresses the challenge of performance prediction in CDNs using machine learning techniques. By leveraging business request data, load information, and other relevant features, our approach aims to predict key performance indicators, such as CPU utilization, bandwidth usage, and I/O operations. We propose a comprehensive feature engineering method that aggregates input metrics across devices, categorizes business requests using clustering, and incorporates time series modeling to capture traffic patterns. Extensive experiments demonstrate the effectiveness of our approach, highlighting its potential to enhance resource management and service quality in CDNs, thereby supporting the deployment of meta computing in IIoT.

Byzantine fault-tolerant (BFT) consensus is a critical problem in parallel and distributed computing systems, particularly with potential adversaries. Most prior work on BFT consensus assumes reliable message delivery and tolerates arbitrary failures of up to$\frac{n}{3}$nodes out of$n$total nodes. However, many systems face unpredictable message delivery failures. This paper investigates the impact of unpredictable message delivery failures on the BFT consensus problem. We propose Nicaea, a novel protocol enabling consensus among loyal nodes when the number of Byzantine nodes is below a new threshold, given by:$\frac{\left(2-\rho\right)\left(1-\rho\right)^{2n-2}-1}{\left(2-\rho\right) \left(1-\rho\right)^{2n-2}+1}n$, where$\rho$denotes the message failure rate. Theoretical proofs and experimental results validate Nicaea's Byzantine resilience. Our findings reveal a fundamental trade-off: as message delivery instability increases, a system's tolerance to Byzantine failures decreases. The well-known$\frac{n}{3}$threshold under reliable message delivery is a special case of our generalized threshold when$\rho=0$. To the best of our knowledge, this work presents the first quantitative characterization of unpredictable message delivery failures’ impact on Byzantine fault tolerance in parallel and distributed computing.

Federated Learning (FL) is a new learning framework in which$s$clients collaboratively train a model under the guidance of a central server. Meanwhile, with the advent of the era of large models, the parameters of models are facing explosive growth. Therefore, it is important to design federated learning algorithms for edge environment. However, the edge environment is severely limited in computing, storage, and network bandwidth resources. Concurrently, adaptive gradient methods show better performance than constant learning rate in non-distributed settings. In this paper, we propose a pruning-based distributed Adam (PD-Adam) algorithm, which combines model pruning and adaptive learning steps to achieve asymptotically optimal convergence rate of$O(1/\sqrt[4]{K})$. At the same time, the algorithm can achieve convergence consistent with the centralized model. Finally, extensive experiments have confirmed the convergence of our algorithm, demonstrating its reliability and effectiveness across various scenarios. Specially, our proposed algorithm is$2$% and$18$% more accurate than the current state-of-the-art FedAvg algorithm on the ResNet and CIFAR datasets.

Decentralized federated learning (DFL) has gained significant attention due to its ability to facilitate collaborative model training without relying on a central server. However, it is highly vulnerable to backdoor attacks, where malicious participants can manipulate model updates to embed hidden functionalities. In this paper, we propose BaDFL, a novel Backdoor Attack defense mechanism for Decentralized Federated Learning. BaDFL enhances robustness by applying strategic model clipping at the local update level. To the best of our knowledge, BaDFL is the first decentralized federated learning algorithm with theoretical guarantees against model poisoning attacks. Specifically, BaDFL achieves an asymptotically optimal convergence rate of$O(\frac{1}{\sqrt{nT}})$, wherenis the number of nodes andTis the global maximum iteration number. Furthermore, we provide a comprehensive analysis under two different attack scenarios, showing that BaDFL maintains robustness within a specific defense radius. Extensive experimental results show that, on average, BaDFL can effectively defend against model poisoning within 6 mitigation rounds, with less than a 1% drop in accuracy.

The openness of wireless networks opens the door to Byzantine attacks on the physical channels, making the communications unreliable and resulting in more challenges in achieving consensus among mobile devices. To address this issue, this paper studies the Byzantine-fault-tolerant (BFT) consensus problem based on an unreliable Byzantine communication model. Different from the previous works requiring stable communications between the honest nodes, considering the unreliable communication makes our problem more realistic but also harder. Based on the unreliable communication model, we first implement a BFT abstract MAC (absMAC) layer with a distributed and randomized multi-channel communication algorithm. In the implemented absMAC layer, its acknowledgement and progress operations can be completed within$O\left ({{\frac {kn}{k-f}\log n}}\right)$and$O\left ({{\frac {k}{k-f}\log n}}\right)$rounds, respectively. n, f, and k are the numbers of nodes, Byzantine nodes, and channels, respectively. With the implemented absMAC layer, an efficient and elegant BFT consensus algorithm is designed, which can solve the binary consensus problem within$O\left ({{\frac {kn}{k-f}\log n}}\right) ^{^{^{^{}}}}$rounds in expectation. Even though a series of works have discussed how to achieve consensus with a specific absMAC layer provided, to the best of our knowledge, this paper is the first one that implements a BFT absMAC layer.

As a distributed computing paradigm, federated learning (FL) enables multiple clients to cooperatively train in edge scenarios without sharing raw training data. Nonetheless, FL is vulnerable to Byzantine attacks due to its distributed nature. While numerous solutions have been proposed, they ignore the inconsistency of local models among clients caused by data heterogeneity (i.e., Non-IID), which severely degrades the performance of FL. Moreover, to further protect client privacy, complex security algorithms are integrated into FL, which seriously increases the privacy computation overhead on edge nodes. To tackle the above issues, this paper proposes a lightweight privacy-preserving federated learning framework, named LPP-FL, significantly improving the performance of FL against Byzantine attacks with Non-IID data. Specifically, we incorporate a correction-term into local model training to mitigate the inconsistency of local models among clients caused by data heterogeneity. Moreover, we design a secure protocol that is deployed on two servers, which achieves Byzantine-robust aggregation results while providing lightweight privacy protection for clients. Theoretical analysis demonstrates the security and robustness of LPP-FL. Extensive experiments show that LPP-FL exhibits superior performance against Byzantine attacks across various data distributions.

Vision-and-Language Navigation (VLN) is a challenging task where an agent is required to navigate to a natural language described location via vision observations. The navigation abilities of the agent can be enhanced by the relations between objects, which are usually learned using internal objects or external datasets. The relationships between internal objects are modeled employing graph convolutional network (GCN) in traditional studies. However, GCN tends to be shallow, limiting its modeling ability. To address this issue, we utilize a cross attention mechanism to learn the connections between objects over a trajectory, which takes temporal continuity into account, termed as Temporal Object Relations (TOR). The external datasets have a gap with the navigation environment, leading to inaccurate modeling of relations. To avoid this problem, we construct object connections based on observations from all viewpoints in the navigational environment, which ensures complete spatial coverage and eliminates the gap, called Spatial Object Relations (SOR). Additionally, we observe that agents may repeatedly visit the same location during navigation, significantly hindering their performance. For resolving this matter, we introduce the Turning Back Penalty (TBP) loss function, which penalizes the agent’s repetitive visiting behavior, substantially reducing the navigational distance. Experimental results on the REVERIE, SOON, Touchdown and R2R datasets demonstrate the effectiveness of the proposed method.

Many emerging applications in edge computing require processing of huge volumes of data generated by end devices, using the freshest available information. In this paper, we address the distributed optimization of multi-user long-term average Age-of-Information (AoI) objectives in edge networks that use NOMA transmission. This poses a challenge of non-convex online optimization, which in existing work often requires either decision making in a combinatorial space or a global view of entire network states. To overcome this challenge, we propose a reinforcement learning-based framework that adopts a novel hierarchical decomposition of decision making. Specifically, we propose three different types of distributed agents to learn with respect to efficiency of AoI scheduling, fairness of AoI scheduling, as well as a high-level policy balancing these potentially conflicting design objectives. Not only does the proposed decomposition improve learning performance due to disentanglement of different design objectives/rewards, but it also enables the algorithm to learn the best policy while also learning the explanations – as actions can be directly compared in terms of the design objectives. Our evaluations show that the proposed algorithm improves the long-term average AoI by$200\%{-}300\%$and 400% compared to prior works with NOMA and the optimal solution without NOMA, respectively.

As an integration of digital twin and edge computing, the digital twin edge networks (DITENs) have been proposed in recent years to fill the gap between physical edge networks and digital systems. Meanwhile, the multi-access wireless environments in edge computing make it hard to provide ultra-reliable and low-latency communications for digital twin, especially when the jamming attacks can be launched by the adversaries. This paper studies the jamming-resilient physical-to-virtual communication (PTVC) problem in DITENs despite strong cooperative jamming. Note that the previous jamming models mainly focus on the jamming behaviors from individual adversaries and are restricted by the energy budget limitation and uniform jamming assumption. In this paper, we consider a more comprehensive jamming model, in whichfadversaries can cooperatively launch their jamming attacks in totallykwireless channels with unlimited power budget and non-uniform jamming signals. Then, based on the new proposed$(k,f)$-cooperative jamming model, we show that$k\gt f$is the necessary and also sufficient condition to solve the PTVC problem. On one hand, we prove that the PTVC problem is insoluble when$f\leq k$; on the other hand, two distributed algorithms are given as the solutions of the PTVC problem amongnphysical objectives and one sink node when$k\gt f$, the time complexity of which are$O\left ({{\frac {n \log n}{k (\log k-\log f)}}}\right)$and$O\left ({{\frac {n \log n}{\log k-\log f}}}\right)$based on the communication modes with/without acknowledgement, respectively. Both of the theoretical results and empirical simulations are conducted to show the resilience of our algorithms despite such a strong cooperative jamming model.

In this paper, we study a stable Age-of-Information (AoI) scheduling problem to handle the massive packet aggregation from arbitrary total ofnend devices to an edge device via a single hop wireless channel when information constantly arrives at the end side. Specifically, we consider the arrivals of the information with anonlineinjection mode, i.e., information is injected to end devices with an unknown injection rate in each time slot. After the information is injected, the AoI with respect to those end devices constantly increases until their fresh messages are received by the edge device, which characterizes the freshness of the information at destination. Based on the online injection mode, we propose the first distributed stable AoI scheduling algorithm combining NOMA (Non-Orthogonal Multiple-Access) technique in this paper, to minimize the expected average peak AoI (EAP-AoI) of our end-to-edge information system. Adopting NOMA technique enableskmessages decoded from a mixed signal by the edge device in our algorithm, with parameter$k\gt 1$. We prove that our algorithm is stable even under the asymptotically maximum injection rate of$O(k/n)$that any stable AoI scheduling algorithm may handle, and the EAP-AoI of our information system is bounded by$O(\sqrt [{3}]{nk})$time slots under the injection rate of$O(k/n)$. Comparing with two existing results, the EAP-AoI in our algorithm is$O\left ({{\frac {n^{2/3}}{k^{4/3}}}}\right)$and$O\left ({{\frac {n^{2/3}}{k^{1/3}}}}\right)$times smaller. Numerical results also verify the stability and efficiency of our algorithm.

Value function factorization has achieved great success in multi-agent reinforcement learning by optimizing joint action-value functions through the maximization of factorized per-agent utilities. To ensure Individual-Global-Maximum property, existing works often focus on value factorization using monotonic functions, which are known to result in restricted representation expressiveness. In this paper, we analyze the limitations of monotonic factorization and present ConcaveQ, a novel non-monotonic value function factorization approach that goes beyond monotonic mixing functions and employs neural network representations of concave mixing functions. Leveraging the concave property in factorization, an iterative action selection scheme is developed to obtain optimal joint actions during training. It is used to update agents’ local policy networks, enabling fully decentralized execution. The effectiveness of the proposed ConcaveQ is validated across scenarios involving multi-agent predator-prey environment and StarCraft II micromanagement tasks. Empirical results exhibit significant improvement of ConcaveQ over state-of-the-art multi-agent reinforcement learning approaches.

Due to the surge in mobile apps, online videos, and cloud gaming, central servers struggle with high traffic demands. Content delivery networks (CDNs) mitigate this by distributing content from edge caches, easing backbone network strain. Yet, current allocation algorithms, constrained by practical complexities and billing, often fail to optimally schedule traffic, causing server overload and increased costs. Our solution, CEQC-CDN, addresses these issues by considering DNS load balancing, regional hijacking, quality constraints, and server capacity limits. By incorporating these factors as linear constraints through binary decomposition and variable introduction, CEQC-CDN achieves global optimal traffic scheduling. Employing a greedy policy for monthly optimization, tests demonstrate an 8.57% reduction in CDN traffic costs versus conventional greedy algorithms.

The self-attention mechanism distinguishes transformer-based large language models (LLMs) apart from convolutional and recurrent neural networks. Despite the performance improvement, achieving real-time LLM inference on silicon remains challenging due to the extensive use of Softmax in self-attention. In addition to the non-linearity, the low arithmetic intensity significantly limits processing parallelism, especially when working with longer contexts. To address this challenge, we propose Constant Softmax (ConSmax), a software-hardware co-design that serves as an efficient alternative to Softmax. ConSmax utilizes differentiable normalization parameters to eliminate the need for maximum searching and denominator summation in Softmax. This approach enables extensive parallelization while still executing the essential functions of Softmax. Moreover, a scalable ConSmax hardware design with a bitwidth-split look-up table (LUT) can achieve lossless non-linear operations and support mixed-precision computing. Experimental results show that ConSmax achieves a minuscule power consumption of 0.2mW and an area of 0.0008mm2 at 1250MHz working frequency in 16nm FinFET technology. For open-source contribution, we further implement our design with the OpenROAD toolchain under SkyWater's 130nm CMOS technology. The corresponding power is 2.69mW and the area is 0.007mm2. ConSmax achieves 3.35× power savings and 2.75× area savings in 16nm technology, and 3.15× power savings and 4.14× area savings with the open-source EDA toolchain. In the meantime, it also maintains comparable accuracy on the GPT-2 model and the WikiText103 dataset. The project is available at https://github.com/ReaLLMASIC/ConSmax.

Due to its decentralized framework and outdoor environments, federated edge learning (FEEL) faces significant vulnerability to malicious attacks within edge networks. Prevailing FEEL approaches typically hinge on a dependable parameter server (PS) to contend with the adversarial updates from Byzantine clients. Recognizing the inherent unreliability of PSs in edge networks, this paper delves into the security challenges of FEEL, specifically addressing Byzantine PSs. We present a Byzantine fault-tolerant FEEL algorithm, named Fed-MS, in which a multi-server technique along with a newly designed trimmed-mean-based model filter is employed. This combination ensures that each client can obtain a feasible global model for its local training, closely approximating a true model aggregated by benign PSs. Furthermore, we propose a sparse uploading strategy in Fed-MS to enhance communication efficiency for model aggregation to multiple PSs. Theoretical analysis demonstrates that, when Byzantine PSs are a minority, Fed-MS achieves an expected convergence speed of$O(1/T)$with$T$defined as the number of training rounds, akin to state-of-the-art works under non-Byzantine settings. Extensive experiments are conducted on the CIFAR-10 dataset with MobileNet V2 as the training model. The numerical results show that our Fed-MS can improve the model accuracy from 10% to at least 76% under the malicious attacks from Byzantine PSs. Our code is released at https://github.com/haoma2772/Fed-MS.

QUIC is the underlying protocol of the next generation HTTP/3, serving as the major vehicle delivering video data nowadays. As a userspace protocol based on UDP, QUIC features low transmission latency and has been widely deployed by content providers. However, the high computational overhead of QUIC shifts system knobs to CPUs in high-bandwidth scenarios. When CPU resources become the constraint, HTTP/3 exhibits even lower throughput than HTTP/1.1. In this paper, we carefully analyze the performance bottleneck of QUIC and find it results from ACK processing, packet sending, and data encryption. By reducing the ACK frequency, activating UDP generic segmentation offload (GSO), and incorporating PicoTLS, a high-performance encryption library, the CPU overhead of QUIC could be effectively reduced in stable network environments. However, simply reducing the ACK frequency also impairs the transmission throughput of QUIC under poor network conditions. To solve this, we develop LiteQUIC, which involves two mechanisms towards alleviating the overhead of ACK processing in addition to GSO and PicoTLS. We evaluate LiteQUIC in the DASH-based video streaming, and the results show that LiteQUIC achieves 1.2× higher average bitrate and 93.3% lower rebuffering time than an optimized version of QUIC with GSO and PicoTLS.

To address the online learning problem in distributed systems, Streaming Federated learning (SFL) enables immediate model training by clients upon collecting new data, finding wide applications in AI-enabled Internet-of-Things and sensor networks. Given the variability in data distribution across different historical periods, the ability to recall and rapidly apply previously encountered data distributions significantly enhances the efficiency and accuracy of model training. In this paper, a demo based on the real-world temperature datasets is presented to demonstrate the importance of history knowledge in local training and the federating process of SFL, which also shows that vanilla federated learning without considering the history knowledge may even be harmful to model training. Observing this, we propose Fed-HIST, a Federated learning framework that enables the clients to learn from the HISTory knowledge of the whole distributed learning system. Unlike direct raw data storage, Fed-HIST employs model architectures to capture the data distributions, offering a more space-efficient and privacy-preserving method of knowledge storage on a server pool. Additionally, a model similarity comparison scheme is designed to retrieve beneficial knowledge from the pool uploaded by the clients in the past. Such a history-aware federation can enhance the efficiency of training each client, only requiring the recurrence of similar data distributions among SFL participants. We validate our framework through extensive simulations on MNIST, Fashion-MINST, CIFAR10, and CIFAR100 datasets, benchmarking against 9 baselines and highlighting the importance of federating from history in SFL problem through necessary ablation studies.

Wireless networks have become integral to modern communication systems, enabling the seamless exchange of information across a myriad of applications. However, the inherent characteristics of wireless channels, such as fading, interference, and openness, pose significant challenges to achieving fault-tolerant consensus within these networks. Fault-tolerant consensus, a critical aspect of distributed systems, ensures that network nodes collectively agree on a consistent value even in the presence of faulty or compromised components. This survey paper provides a comprehensive overview of fault-tolerant consensus mechanisms specifically tailored for wireless networks. We explore the diverse range of consensus protocols and techniques that have been developed to address the unique challenges of wireless environments. The paper systematically categorizes these consensus mechanisms based on their underlying principles, communication models, and fault models. It investigates how these mechanisms handle various types of faults, including communication errors, node failures, and malicious attacks. It highlights key use cases, such as sensor networks, Internet of Things applications, wireless blockchain, and vehicular networks, where fault-tolerant consensus plays a pivotal role in ensuring reliable and accurate data dissemination.

Big data and strong computing power have promoted artificial intelligence to the era of big models. In particular, ChatGPT’s debut heralded the vigorous development of large models. It is an urgent problem to train large models with trillion-level parameters efficiently. Traditional single-machine training stores all data and model parameters in memory. However, due to the limitation of memory and communication resources, when the amount of data or model parameters increases, the problem of memory shortage and communication blocking often occurs. Therefore, distributed training is the most effective ways to solve the above problems and improve training efficiency. In this paper, we propose the algorithmDL-DP, which can achieve an asymptotically optimal convergence rate$O(1/{\sqrt{TK\Gamma^*}})$while satisfyingε-differential privacy, whereTis the local epoch number,Kis the global maximum iteration number and$\Gamma^*$is the minimum covering index. In particular, when${\Gamma ^*} = N$, DL-DP achieves a convergence rate of$O(1/{\sqrt{TKN}})$, which is equivalent to the best-known FedAvg approach implemented by training the full model at each client. When${\Gamma ^*} = 1$, DL-DP achieves a convergence rate of$O(1/{\sqrt{TK}})$, which is comparable to OAP that assumes all parameters need to be trained at least once in each iteration. Finally, our algorithm has been demonstrated to converge through extensive experiments.

Federated edge learning (FEEL) is a novel paradigm that enables privacy-preserving and distributed machine learning on end devices. However, FEEL faces challenges from data/system heterogeneity among the participating clients and resource constraints of edge networks, which affect the efficiency and accuracy of the learning process. In this paper, we propose a comprehensive framework for client selection in FEEL based on the concept of Value-of-Information (VoI), which measures how valuable a client is for the global model aggregation. Our framework consists of two independent components: a VoI estimator that uses reinforcement learning to learn the relationship between VoI and various heterogeneous factors of clients; and a greedy client selector that chooses the most valuable clients under network resource constraints. Compared with most of the previous works that use concrete criteria to evaluate and select heterogeneous clients, our VoI-based approach is more comprehensive. Extensive experiments on different datasets and learning tasks are conducted, which show that our framework outperforms several state-of-the-art methods in terms of accuracy.

As an amalgamation of digital twin and edge computing, the digital twin edge networks (DITENs) have drawn much attention from industry and academia to bridge the divide between physical edge networks and digital systems. Meanwhile, the physical hardware and open-access wireless communication environments in edge networks raise significant challenges in timely information aggregation and real-time status updates for digital twins, especially in the presence of inherent failure and hostile jamming. In this paper, we investigate the fault-tolerant Age-of-Information (AoI) optimization problem for digital twin edge networks against the severe fault phenomena in wireless communications. In contrast to previous works that focus on single fault or individual jamming behavior, we propose a comprehensive communication failure model over thefnon-overlapping wireless sub-channels, wheref1out of thefsub-channels are inherently failed andf2out of thefsub-channels are jammed by adversaries. Then, based on the multi-channel communication failure model, we present a distributed fault-tolerant communication algorithm to minimize the expected average peak AoI in DITENs. Using an adaptive transmission strategy, we prove that the AoI optimization issue fornend devices can be resolved within Θ(n) time steps whenf1+f2f. Both theoretical analyses and empirical simulations are conducted to verify the fault-tolerance and efficiency of our proposed algorithm despite the communication failures.

This paper addresses the problem of reliable communications for cooperative learning on Internet-of-Vehicles, where a large amount of data from users and services needs to be processed. Previous works have proposed various cooperative learning schemes, but they often assume that the communications between vehicles are reliable, without considering how to achieve this in an Internet-of-Vehicles network. This paper is the first one that implements an abstract MAC layer using a distributed deep reinforcement learning scheme, which can directly meet the reliable communication requirements of cooperative learning in previous works. Our abstract MAC layer performs two operations:acknowledgement, which makes sure that all vehicles can successfully broadcast their messages to all of their neighbors, andprogress, which ensures that each vehicle can receive at least one message from its neighbors. These operations facilitate vehicles to exchange and update their training models in a cooperative learning service. Our simulation results show the efficiency and fairness of our deep reinforcement learning abstract MAC layer.

Most data center services are finished by the cooperation among the connected servers. However, the malicious attackers always try to divide the network into disconnected components to start some attacks, such as the address resolution protocol (ARP) attack, the denial of service (DoS) attack, the botnet attack, and so on. The connectivity is an excellent indicator to measure the reliability and fault-tolerant ability of the network. Whereas, the traditional connectivity and current conditional connectivity cannot well reflect the fault-tolerant performance of the network when attackers are a block or have a certain structure and the components of the remaining network still have a certain structure. Based on this fact, we propose a new measure: the double-structure connectivity, which can accurately reflect the fault-tolerant ability of the network when attackers are structured and each component of the network has a certain structure after removing the attacked servers. Meanwhile, a hypercube is a high-performance interconnection network that can also be used to design some data center networks. Therefore, we study the double-structure fault-tolerance of the hypercube and determine the double-structure connectivity of distinct structures of the hypercube. Furthermore, we propose algorithms to construct structures of attackers directly to measure the fault-tolerant ability of the hypercube under this attack. Our results can be applied not only to interconnection networks but also to some data center networks.

Edge intelligence is an emerging technology that enables artificial intelligence on connected systems and devices in close proximity to the data sources. Decentralized Collaborative Learning (DCL) is a novel edge intelligence technique that allows distributed clients to cooperatively train a global learning model without revealing their data. DCL has a wide range of applications in various domains, such as smart city and autonomous driving. However, DCL faces significant challenges in ensuring its trustworthiness, as data isolation and privacy issues make DCL systems vulnerable to adversarial attacks that aim to breach system confidentiality, undermine learning reliability or violate data privacy. Therefore, it is crucial to design DCL in a trustworthy manner, with a focus on security, robustness, and privacy. In this survey, we present a comprehensive review of existing efforts for designing trustworthy DCL systems from the three key aformentioned aspects: security, robustness, and privacy. We analyze the threats that affect the trustworthiness of DCL across different scenarios and assess specific technical solutions for achieving each aspect of Trustworthy DCL (TDCL). Finally, we highlight open challenges and future directions for advancing TDCL research and practice.

With the wide deployment of Internet of Things (IoT), blockchain systems have been playing a crucial role to establish a trusted computing environment among potentially mistrusting agents without depending on a centralized server. Different from previous blockchain consensus protocols adopted in IoT, which rely on efficient and stable transmissions, in this article, we consider how to reach blockchain consensus in wireless networks without reliable network support. Specifically, a realistic signal to interference plus noise ratio (SINR) model is adopted to depict the unreliable transmissions in wireless channels. Based on the SINR model, a distributed and randomized consensus algorithm is proposed to reach$k$-times consensus among$n$devices within$O(k+\log n)$time steps with high probability. Note that the time complexity of our algorithm is asymptotically optimal since$\Omega (k+\log n)$is a lower bound to achieve$k$-times consensus in a distributed environment. We conduct both rigorous theoretical analysis and extensive simulations to validate our method. It is believed that our work can facilitate the implementation of blockchains in many wireless scenarios in which the reliable and fast transmissions cannot be guaranteed.

In many edge computing applications, edge devices are required to reach fault-tolerant consensus in order to provide collaborative services in outdoor environments. In this paper, we study a comprehensive$(a,b)$-majority consensus problem based on a novel failure model, which takes$a$distinct opinions as inputs and outputs a$b$-majority opinion as the final agreement. This problem formulation is drastically different from traditional ones, which usually require a majority consensus from the binary opinions of multiple supporters. It is more practical and flexible as it can accommodate more than 2 input opinions and output one that satisfies the application requirement defined by parameter$b$. We also consider physical layer in our failure model while previous models mainly focus on faults occurred in protocol layer and data layer. Based on this more realistic failure model and a more practical consensus problem definition, we present a distributed protocol for$n$edge devices to reach an$(a,b)$-majority consensus within$\Theta (n)$time steps with high probability. Empirical results from our simulation studies validate the fault tolerance property and efficiency of our work in achieving the$(a,b)$-majority consensus.

Known as a distributed ledger technology (DLT), blockchain has attracted much attention due to its properties such as decentralization, security, immutability and transparency, and its potential of servicing as an infrastructure for various applications. Blockchain can empower wireless networks with identity management, data integrity, access control, and high-level security. However, previous studies on blockchain-enabled wireless networks mostly focus on proposing architectures or building systems with popular blockchain protocols. Nevertheless, such existing protocols have obvious shortcomings when adopted in wireless networks where nodes may have limited physical resources, may fall short of well-established reliable channels, or may suffer from variable bandwidths impacted by environments or jamming attacks. In this paper, we propose a novel consensus protocol named Proof-of-Channel (PoC) leveraging the natural properties of wireless communications, and develop a permissioned BLOWN protocol (BLOckchain protocol for Wireless Networks) for single-hop wireless networks under an adversarial SINR model. We formalize BLOWN with the universal composition framework and prove its security properties, namely persistence and liveness, as well as its strengths in countering against adversarial jamming, double-spending, and Sybil attacks, which are also demonstrated by extensive simulation studies.

This paper initiates the study for the basic primitive of distributed message dissemination in multi-hop wireless networks under a strong adversarial jamming model. Specifically, the message dissemination problem is to deliver a message initiating at a source node to the whole network. An efficient algorithm for message dissemination can be an important building block for solving a variety of high-level network tasks. We consider the hard non-spontaneous wakeup case, where a node only wakes up when it receives a message. Under the realistic SINR model and a strong adversarial jamming model that removes the budget constraint commonly adopted in previous work by the adversary, we present a distributed randomized algorithm that can accomplish message dissemination in$\mathscr{T}(O(D(\log n+\log R)))$time slots with a high probability performance guarantee, where$\mathscr{T}(U)$is the number of time slots in the interval from the beginning of the algorithm's execution that contains U unjammed time slots, n is the number of nodes in the network, D is the network diameter,$R$is the distance with respect to which the network is connected. Our algorithm is shown to be almost asymptotically optimal by lower bound$\Omega(D\log n)$for non-spontaneous message dissemination in networks without jamming.

The proliferation of edge computing brings new challenges due to the complexity of decentralized edge networks. Software-defined networking (SDN) takes advantage of pro-grammability and flexibility in handling complicated networks. However, it remains a problem of designing a both trusted and scalable SDN control plane, which is the core component of the SDN architecture for edge computing. In this paper, we propose Curb, a novel group-based SDN control plane that seamlessly integrates blockchain and BFT consensus to ensure byzantine fault tolerance, verifiability, traceability, and scalability within one framework. Curb supports trusted flow rule updates and adaptive controller reassignment. Importantly, we leverage a group-based control plane to realize a scalable network where the message complexity of each round is upper bounded by O(N), where N is the number of controllers, to reduce overheads caused by blockchain consensus. Finally, we conduct extensive simulations on the classical Internet2 network to validate our design.

This article studies decentralized federated learning algorithms in wireless IoT networks. The traditional parameter server architecture for federated learning faces some problems such as low fault tolerance, large communication overhead and inaccessibility of private data. To solve these problems, we propose a decentralized wireless federated learning algorithm called DWFL. The algorithm works in a system where the workers are organized in a peer-to-peer and server-less manner, and the workers exchange their privacy preserving data with the analog transmission scheme over wireless channels in parallel. With rigorous analysis, we show that DWFL satisfies$(\epsilon,\delta)$-differential privacy and the privacy budget per worker scales as$\mathcal {O}(\frac{1}{\sqrt{N}})$, in contrast with the constant budget in the orthogonal transmission approach. Furthermore, DWFL converges at the same rate of$\mathcal {O}(\sqrt{\frac{1}{TN}})$as the best known centralized algorithm with a central parameter server. Extensive experiments demonstrate that our algorithm DWFL also performs well in real settings.

In the past decades, Dynamic Internet of Things (D-IoT) networks have played a conspicuously more important role in many real-life areas, including disaster relief, environment monitoring, public safety, and so on, to rapidly collect information from the environment and help people to make the decision. Meanwhile, due to the widespread implementation of dynamic IoT networks, there exists an enormous demand on designing suitable models and efficient algorithms for fundamental operations in dynamic IoT networks, to achieve the high throughput and reliable low-latency communication demands in 6G networks. In this article, we first present a general dynamic model to comprehensively depict most of the dynamic phenomena in IoT networks. Then, based on the proposed dynamic model, a distributed scheduling algorithm is proposed to competitively optimize the Age-of-Information (AoI) problem in the context of a D-IoT network. We say our scheduling algorithm is competitive: the throughput of the base station approximates the optimal solution with constant competitive ratio; and, the latency for a packet received by the base station is only constant times larger than the optimal latency. Rigorous theoretical analysis and extensive simulations are presented to verify the high throughput and reliable low-latency communications in our proposed algorithm.

Dynamicity is one of the most challenging, yet, key aspects of wireless networks. It can come in many guises, such as churn (node insertion/deletion) and node mobility. Although the study of dynamic networks has been popular in distributed computing domain, previous works considered only partial factors causing dynamicity. In this work, we propose a dynamic model that is comprehensive to include crucial dynamic factors on nodes and links. Our model defines dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a localized dynamic model suits distributed algorithm studies better than a global one. The proposed dynamic model makes use of the more realistic SINR model to describe wireless interference, instead of the oversimplified graph-based models adopted by most existing research. Under the proposed dynamic model, we develop an efficient distributed algorithm accomplishing local broadcast services in the abstract MAC layer that was first presented by Kuhnet al.[24]. Our solution paves the way for many new fast algorithms to solve high-level problems in dynamic networks, such as consensus, single-message broadcast, and multiple-message broadcast. Extensive simulation studies indicate that our algorithm exhibits good performance in realistic environments with dynamic network behaviors.

In this paper, we investigate distributed broadcasting in dynamic networks, where the topology changes continually over time. We propose a network model that captures the dynamicity caused by both churn and mobility of nodes. In contrast to existing work on dynamic networks, our model defines the dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a local dynamic model suits distributed algorithms better than a global one. The proposed dynamic model uses the more realistic SINR model to depict wireless interference, instead of oversimplified graph-based models adopted in most existing work. We consider the fundamental communication primitive of global broadcast, which is to disseminate a message from a source node to the whole network. Specifically, we present a randomized distributed algorithm that can accomplish dynamic broadcasting in an asymptotically optimal running time of$O(D_{T})$with a high probability guarantee, under the assumption of reasonably constantdynamicity rate, where$D_{T}$is thedynamic diameter, a parameter proposed to depict the complexity of dynamic broadcasting. We believe our local dynamic model can greatly facilitate distributed algorithm studies in mobile and dynamic wireless networks.

In this paper, we present the first algorithm to precisely implement the abstract MAC (absMAC) layer under the physical SINR model in dynamic networks. The absMac layer, first presented by (Kuhn et al., 2009), provides reliable local broadcast communications, with timing guarantees stated in terms of a collection of abstract delay functions, based on which high-level algorithms can be designed, independent of specific channel behaviors. The implementation of absMAC requires the design of a distributed algorithm for the local broadcast communication primitives over a particular communication model that defines concrete channel behaviors, and the objective is to minimize the bounds of the abstract delay functions. Halldórsson et al. (2015) showed that under the standard SINR model (synchronous communications without physical carrier sensing or location information), there exist no efficient exact implementations. In this work, we demonstrate that physical carrier sensing, a commonly seen function performed by wireless devices, can help get efficient exact implementation algorithms. Specifically, we propose an algorithm that precisely implements the absMAC layer under the SINR model in dynamic networks. The algorithm provides asymptotically optimal bounds for both acknowledgement and progress functions defined in the absMAC layer. Our algorithm leads to many new faster algorithms for solving high-level problems under the SINR model in dynamic networks. We demonstrate this by exemplifying problems of Consensus, Multi-Message Broadcast, and Single-Message Broadcast. It deserves to point out that our implementation algorithm is designed based on an optimal algorithm for a General Local Broadcast (GLB) problem, which takes the number of distinct messages into consideration for the first time. The GLB algorithm can handle many communication scenarios apart from those defined in the absMAC layer. Simulation results show that our proposed algorithms perform well in reality.

The byzantine model is widely used to depict a variety of node faults in networks. Previous studies on byzantine-resilient protocols in wireless networks assume reliable communications and do not consider the jamming behavior of byzantine nodes. Such jamming, however, is a very critical and realistic behavior to be considered in modern wireless networks. In this paper, for the first time, we integrate the jamming behavior of byzantine nodes into the network setting. We show that, in this much more comprehensive and harsh model, efficient distributed communication protocols can be still devised with elaborate protocol design. In particular, we developed an algorithm that can accomplish the basic multiple-message dissemination task close to the optimal solution in terms of running time. Empirical results validate the byzantine-resilience and efficiency of our algorithm.

This paper presents$\mathit {wChain}$, a blockchain protocol specifically designed for multihop wireless networks that deeply integrates wireless communication properties and blockchain technologies under the realistic SINR model. We adopt a hierarchical spanner as the communication backbone to address medium contention and achieve fast data aggregation within$O(\log N\log \Gamma)$slots where$N$is the network size and$\Gamma $refers to the ratio of the maximum distance to the minimum distance between any two nodes. Besides,$\mathit {wChain}$employs data aggregation and reaggregation as well as node recovery mechanisms to ensure efficiency, fault tolerance, persistence, and liveness. The worst-case runtime of$\mathit {wChain}$is upper bounded by$O(f\log N\log \Gamma)$, where$f=\lfloor \frac {N}{2} \rfloor $is the upper bound of the number of faulty nodes. To validate our design, we conduct both theoretical analysis and simulation studies. The results not only demonstrate the nice properties of$\mathit {wChain}$, but also point to a large new space for the exploration of blockchain protocols in wireless networks.

In this paper, we study distributed algorithms to realize efficient communications under the Rayleigh-fading model. This model extends the popular deterministic SINR model using stochastic propagations to address the fading effects observed in reality. Stochastic propagations can greatly increase the difficulty of handling interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving a distributed and randomized algorithm to implement the abstract MAC (absMAC) layer, which was first proposed by Kuhn et al.. With two basic time-guaranteed communication primitives, namely acknowledgement and progress, which correspond to the operations of node local broadcasts and message receptions from others, the absMAC layer decomposes the algorithm design and analysis in networks into two independent components, i.e., implementing the absMAC layer over a physical network and designing algorithms with the help of the two primitives in the absMAC layer. Thus, it sharply reduces the fussy and complicated process of algorithm design and analysis over the physical network. Our proposed algorithm implements the absMAC layer under the Rayleigh-fading model with no more than a logarithmic factor inferior to the optimal solution in terms of time complexity. The presented simulation results indicate that our algorithm performs well in realistic environments. Furthermore, we show that by making full use of our proposed absMAC layer algorithm, many network primitives such as Neighbor Discovery, Single/Multiple-Message Broadcast, and Consensus, can be efficiently implemented.

Network function virtualization (NFV) is a promising virtualization technology that has the potential to significantly reduce the expenses and improve service agility. The NFV makes it possible for Internet service providers (ISPs) to employ various virtual network functions (VNFs) without installing new equipments. One of the most attractive approaches in the NFV technology is the so-called joint placement and allocation of virtual network functions (JPA-VNFs), which considers the balance between VNF investment with Quality of Services (QoS). We introduce a novel capability function to measure the potential of locating VNF instances for each server in the proposed OJPA-HS model. This model allows the servers in the network to be heterogeneous, at the same time combines and generalizes many classical JPA-VNF models. Despite its NP-hardness, we present a provable best-possible deterministic online algorithm based on dynamic programming (DP). To conquer the high complexity of DP, we propose two additional randomized heuristics, Las Vegas (LV) and Monte Carlo (MC) randomized algorithms, which perform even as good as DP with much smaller complexity. Besides, MC is a promising heuristic in practice as it has the advantage to deal with the big data environment. Extensive numerical experiments are constructed for the proposed algorithms in this article.

In smart city services, information systems can provide efficient and effective support during an emergency, and an emergency management system can make use of any available infrastructure network, such as the Internet of Things. However, ordinary communication infrastructures can be prone to disruptions or even failures during emergencies. Hence, it is necessary to present a fallback system in case of such failures. In this article, we propose such a fallback design for emergency management that relies on short-range multihop wireless communications. Specifically, we model the crowd by a multihop ad hoc network consisting of nodes (i.e., civilians with smartphones or wearable devices) that are capable of short-range communications, and address the problem of how to “diffuse” the crowd in an efficient and distributed fashion. The problem is subdivided into crowd density computation and crowd diffusion. We treat the area as a grid that is divided into square cells. Crowd density computation is to compute the density of each cell, for which we present efficient distributed algorithms that compute the density of each grid cell exactly. With the computed densities, crowd diffusion is to design a load-balancing strategy (to direct local movements of individual civilians) such that in a short time the nodes/civilians will become evenly distributed over the entire area. We present a distributed diffusion algorithm that has good performance. We conduct extensive simulations to evaluate the proposed algorithms, and the results corroborate our theoretical analyses.

This paper studies jamming-resilient distributed backbone construction in multi-hop wireless networks. Specifically, a strong adversarial jamming model is proposed that captures the general jamming phenomena suffered by wireless communications. The jamming model is based on the realistic Signal-to-Interference-plus-Noise-Ratio (SINR) interference model, and is featured by local-uniformity, unrestricted energy budget and reactivity, which covers more jamming scenarios and is much closer to reality than existing jamming models. Under the strong adversarial jamming model, we propose a randomized distributed algorithm that can construct a backbone in J(O(log n + logR)) rounds with high probability, where J(O(log n + log R)) is the number of rounds in the interval from the beginning of the algorithm execution that contains O(log n + log R) unjammed rounds for every node. This result is asymptotically optimal considering the trivial lower bound of Ω(log n) for a successful transmission even without interference and jamming.

This paper investigates distributed Dominating Set (DS) and Connected Dominating Set (CDS) construction in dynamic wireless networks under the SINR interference model. Specifically, we present a new model for dynamic networks that admits both churns (due to node arrivals/departures) and node mobility. Under this dynamic model, we propose efficient algorithms to construct a DS and a CDS with constant approximation ratios w.r.t. the corresponding minimum ones in O(log n) time with a high probability guarantee. To the best of our knowledge, these algorithms are the first known ones for DS and CDS construction in dynamic networks assuming the SINR interference model. We believe our dynamic network model can greatly facilitate distributed algorithm studies in mobile and dynamic wireless networks.

Dynamicity is one of the critical characteristics and a major challenge in designing communication protocols in wireless networks. Most of the previous works had focused on the internal node changes (e.g., mobility, arrival, or departure) and not considered the effect of external environmental change. However, the external environmental change, in general, is a more complex phenomenon that can impede nodes from successful communication, implying the protocols of the previous dynamic models do not work well in practice. In this paper, we give an algorithm for distributed broadcasting in a more general model with fully dynamic wireless networks, called FD-Broadcast. Specifically, we present a fully dynamic model which allows node mobility and churns (due to node arrivals/departure) and external environmental change. In contrast to the previous works on dynamic networks, our model defines the full dynamicity in terms of localized topological changes of each node and can tolerate some external environmental change. The external environment changes are captured by the random jamming method. We show that FD-Broadcast can achieve broadcasting in$O(D_{S})$rounds with a high probability guarantee under the assumption of constant dynamic rate in the SINR model, where$D_{S}$is the dynamic diameter, a parameter proposed to depict the complexity of dynamic broadcasting. Moreover, the lower bound of dynamic broadcasting is proved to be$\Omega(D_{S})$, thus, FD-Broadcast is asymptotically optimal with high probability.

This paper presents the first distributed algorithm to construct a spanner for arbitrary ad hoc networks under the physical signal-to-interference-and-noise-ratio (SINR) interference model. Spanner construction is one of the most important techniques for topology control in wireless networks, which intends to find a sparse topology in which only a small number of links need to be maintained, without substantially degrading the path connecting any pair of the nodes in the network. Due to the non-local property of interference, constructing a spanner is challenging under the SINR model, especially when a local distributed algorithm is desired. We meet this challenge by proposing an efficient randomized distributed algorithm that can construct a spanner in O(log n log Γ) timeslots with a high probability, where n is the total number of nodes and Γ describes the ratio of the maximum distance to the minimum distance between nodes. The constructed spanner concurrently satisfies two most desirable properties: constant stretch and linear sparseness. Our algorithm employs a novel maximal independent set (MIS) procedure as a subroutine, which is crucial in achieving the time efficiency of spanner construction. The MIS algorithm improves the best known result of O(log2n) [33] to O(log n) and is of independent interest as the algorithm is applicable also to many other applications. We conduct simulations to verify the proposed spanner construction algorithm, and the results show that our algorithm also performs well in realistic environments.