Coordinated beamforming in multi-access-point (AP) systems has been proposed to address the high throughput and low latency demands of future wireless networks. To tackle the challenge of distributed fair user scheduling with reduced overhead, a multi-agent reinforcement learning (MARL)-based user scheduling scheme is introduced for a two-AP setup. This approach aims to determine user scheduling and power allocation at each AP distributively across consecutive time slots to enhance sum rates while ensuring fairness. In particular, it employs Multi-Agent Deep Deterministic Policy Gradient (MADDPG) with a multi-head self-attention mechanism to map channel information to AP behaviors. Additionally, a general CSI collection and information exchange scheme between the two APs is proposed to guarantee acquisition of necessary information. Simulation results illustrate the effectiveness of the proposed coordination framework, demonstrating learning convergence, and improvements of data rate optimization and fairness.

Next-generation IEEE 802.11 wireless local area network (WLAN) amendments have been proposed to support Wi-Fi stations (STAs) and access points (APs). IEEE 802.11be (Wi-Fi 7) features multi-link operation (MLO) with multi-link device (MLD), where the enhanced multi-link single-radio (EMLSR) operation is promising. Also, IEEE 802.11bf launches a sensing capability, paving the way for integrated sensing and communications (ISAC). Pioneering an innovative combination of EMLSR operation and ISAC functionality in this paper, we propose WiHound, a novel method for target tracking with ISAC using EMLSR in IEEE 802.11 WLANs. Specifically, we adopt the Kalman filter for target tracking and develop a score-based ISAC decision approach for the AP MLD to decide between sensing and communications within each transmit opportunity (TXOP). For a sensing TXOP, we solve a discrete convex optimization problem based on Cramér-Rao lower bound (CRLB) to select three STA MLDs required in trilateration. Conversely, for a communications TXOP, we develop an efficient fairness-aware STA MLD selection heuristic approach toward weighted proportional fairness. Simulation results confirm the superiority of WiHound on striking a balance between sensing and communications. Moreover, we investigate the effect of number of STA MLDs on the sensing performance of WiHound.

The IEEE 802.11bf amendment is aimed to provide Wi-Fi networks with essential support for their potential sensing capability, in addition to their renowned communications paradigm. Taking advantage of both sensing and communications, integrated sensing and communications (ISAC) is a promising direction for Wi-Fi that has been less investigated in the existing literature. Therefore, in this paper, we propose a novel method for target tracking with ISAC in IEEE 802.11bf. Particularly, the Kalman filter is adopted for tracking the state of the target and the Cramér-Rao lower bound (CRLB) is employed to develop a proper performance metric for trilateration, where the access point (AP) needs a selection of three stations (STAs). By solving a discrete convex optimization problem, the AP decides between sensing and communications within each TXOP and selects the three STAs for trilateration if sensing is conducted. Simulation results confirm that the proposed method strikes a good balance between the sensing and communications performance. Moreover, the sensing performance of the proposed method improves as the number of STAs increases.

This paper introduces a novel over-the-air computation method that utilizes low-complexity transmissive intelligent surfaces (TISs) for neural network inference. It is demonstrated that the signal propagation model through TIS closely resembles the fully connected layer of neural networks. And through training, the TIS phase shifts can be determined to perform a specific computation on radio-frequency (RF) signals. Considering the practical constraints of TIS designs with continuous phase shifts in millimeter-wave (mmWave) frequency, we propose a novel discretized complex-valued neural network structure and a training method suitable for low-complexity 1-bit and 2-bit TIS-based neural network layers. It is shown through simulation that the proposed method achieves high accuracy on an image classification task even for 1-bit or 2-bit TISs.

A novel convolutional layer based on transmissive intelligent surfaces (TISs), which operates in the radio-frequency (RF) domain, is introduced for analog over-the-air (OTA) computation in this paper. To be specific, each RF convolutional layer comprises three TISs placed sequentially to perform a 2-D convolution operation. A method for designing TIS transmission coefficients, TIS locations, and TIS element spacing is proposed to execute the 2-D convolution of I ∗ K = O. The transmission coefficients of the second TIS encapsulate information about the kernel K, and the output (O) of the third TIS is the convolutional result of K and the input signal (I), which is the input to the first TIS. To validate the proposed design, a simple neural network featuring a single convolutional layer with one kernel is tested. The simulation results demonstrate that, with a practical size of the proposed design and adequate signal power transmitted to the TISs, the neural network incorporating the proposed TIS-based convolutional layer achieves a good approximation of performance compared to a neural network with the classic complex-valued convolutional layer. This validates the feasibility of the proposed design and the potential for offloading convolution operations from digital processors to the RF domain.

A low-complexity direction of arrival (DoA) estimation approach based on transmissive intelligent surfaces (TISs) is proposed for single-target scenarios. The proposed DoA estimator is composed of one TIS with pre-designed phase shifts and two receive antennas. The signal from the target transmits through the TIS before being captured by the two antennas, and the DoA of the target is estimated solely based on the ratio of power received at the two antennas. An optimization method is proposed to design the phase shifts of the TIS and the relative positions of the two antennas with two primary objectives: (1) enhancing DoA estimation accuracy, and (2) guaranteeing an analytical expression of the estimated DoA derived from the power ratio. To be specific, the power ratio is approximated using a limited number of Fourier series coefficients, so that the optimization problem is formulated as a small set of quadratic programming problems aimed at optimizing these Fourier series coefficients. Simulation results validate the effectiveness of the proposed TIS-based DoA estimator and the optimization method. The method demonstrates comparable or even lower root mean squared error (RMSE) of DoA estimation in comparison to classic approaches. Unlike classic approaches that rely on complex-valued received signals, the proposed method offers reduced hardware complexity, relying solely on power measurements. Additionally, it involves reduced computational complexity compared to classic approaches including the multiple signal classification (MUSIC) algorithm and the discrete Fourier transform (DFT)-based DoA estimation method.

Reconfigurable intelligent surfaces (RISs) have been proposed to enhance coverage performance in millimeter-wave bands by providing alternative links between access points and user devices in non-line-of-sight (NLOS) scenarios. However, the previously-studied reflective RISs (R-RISs) only offer 180° coverage, with most studies focusing on links with one R-RIS. Recently, transmissive-reflective RISs (T-RISs) that can provide 360° coverage have been proposed. In order to understand performance limits of both types of RISs, stochastic geometry is employed to analyze connection probability when R-RISs and T-RISs are used with single-RIS and multi-RIS links. The connection probability for single-RIS links and an upper bound on connection probability for multi-RIS links are derived with sparse obstacle distributions where independence of line-of-sight (LOS) statuses of different links can be assumed. The theoretical analysis is validated by simulations. Additionally, a comparison is provided between single-RIS and two-RIS links, as well as between R-RISs and T-RISs. Numerical evaluation using Nakagami fading propagation and a sectored antenna model shows that single-RIS links offer substantial coverage improvement for shorter-distance communications, whereas two-RIS links are more effective for longer-range communications. Moreover, numerical results demonstrate that, under the same model, T-RISs exhibit significantly improved coverage compared to R-RISs, especially with denser obstacle distribution.

Reconfigurable intelligent surfaces (RISs) are an emerging technology to improve coverage in millimeter-wave bands, by providing reflective links between access points and user devices when line-of-sight (LoS) links are blocked. To understand the limits of multi-RIS coverage performance in mmWave wireless local area networks (WLANs), we employ stochastic geometry to analyze connection probability with both single-RIS and multi-RIS links with a sparse obstacle distribution. The connection probability for single-RIS links and an upper bound on connection probability for multi-RIS links are derived under an approximation where independence of LoS statuses of different links is assumed. Numerical simulations validate the analytical results and provide a comparison between single-RIS and multi-RIS links. Results demonstrate that single-RIS links provide substantial coverage increases for relatively short-distance communications but are not as effective for longer distances. Meanwhile, two-RIS links can provide substantially increased coverage for longer-range communications, but do not exhibit a significant advantage compared with single-RIS links for short distances.

To cope with growing wireless bandwidth demand, millimeter wave (mmWave) communication has been identified as a promising technology to deliver Gbps throughput. However, due to the susceptibility of mmWave signals to blockage, applications can experience significant performance variability as users move around due to rapid and significant variation in channel conditions. In this context, proactive schedulers that make use of future data rate prediction have potential to bring a significant performance improvement as compared to traditional schedulers. In this work, we propose an efficient proactive algorithm that prioritizes the scheduling of scarce resources to achieve better performance than traditional schedulers. The results show that our scheduler can increase average data rate by up to 20% compared to non-proactive scheduling and achieves from 60% to 75% of the performance gain of an optimal proactive scheduler.

Reconfigurable intelligent surfaces (RISs) have been a promising technology to maintain connection performance for millimeter wave (mmWave) communication in non-line-of-sight (NLoS) case by providing an indirect link between access point and user. In this paper, we explore the advantage of multi-RIS deployment to improve connection probability in a scenario with randomly distributed obstacles by solving a modified thinnest covering problem. Optimal RIS deployment in 3D scenario up to six RISs and selection of RIS number based on room size are investigated analytically. A heuristic optimization method of RIS size and orientation is also proposed to guarantee adequate received signal strength. The proposed deployment strategy is validated by simulation that connection probability is significantly improved with only very few RISs.

As vehicles are embedded with an increasing number of sensors and more powerful processors, computation-intensive on-board applications are being deployed. Emerging cooperative processing capabilities among vehicles will increase computing capability even further. In this paper, we present a novel framework for task-oriented group formation, where groups of vehicles are tailored for a specific cooperative computation task to be performed. We use the framework to develop a vehicular group formation algorithm that improves the quality of the computation result while achieving a specified probability of successful task completion. A prototype of the group formation algorithm for a generic distributed learning application example is implemented and extensively evaluated. Results show that our approach is able to significantly increase the percentage of successfully completed tasks compared to two baseline approaches.

This paper studies the effects of millimeter-wave (mm-wave) beam alignment errors on the downlink achievable rate of a heterogeneous network (HetNet), which consists of sub-6 GHz macro-cells and mm-wave small-cells. The alignment error is modeled as a function of the underlying mm-wave link parameters. The conventional maximum biased received power criterion, where the bias is used for mm-wave small-cells, is adopted for cell associations. By varying the value of the bias factor, we investigate the changes in the downlink rate coverage probability. Our simulation results indicate that high values (of the order of 30 dB) for the bias, while beneficial in the case of perfect alignment, are actually disadvantageous for the low-rate users in the case of imperfect beam alignment. The low-rate users are better served by a moderate value (of the order of 20 dB) of the bias when the beam alignment errors are accounted for. We also show that the above disparity can be narrowed down by increasing by mm-wave base station (BS) antennas$a$nd/or the mm-wave BS density.

Reconfigurable intelligent surfaces (RISs) have been proposed to increase coverage in millimeter-wave networks by providing an indirect path from transmitter to receiver when the line-of-sight (LoS) path is blocked. In this paper, the problem of optimizing the locations and orientations of multiple RISs is considered for the first time. An iterative coverage expansion algorithm based on gradient descent is proposed for indoor scenarios where obstacles are present. The goal of this algorithm is to maximize coverage within the shadowed regions where there is no LoS path to the access point. The algorithm is guaranteed to converge to a local coverage maximum and is combined with an intelligent initialization procedure to improve the performance and efficiency of the approach. Numerical results demonstrate that, in dense obstacle environments, the proposed algorithm doubles coverage compared to a solution without RISs and provides about a 10% coverage increase compared to a brute force sequential RIS placement approach.

Although the millimeter wave (mmWave) band has great potential to address ever-increasing demands for wireless bandwidth, its intrinsically unique propagation characteristics call for different scheduling strategies in order to minimize performance drops caused by blockages. A promising approach to mitigate the blockage problem is proactive scheduling, which uses blockage predictions to schedule users when they are experiencing good channel conditions. In this paper, we formulate an optimal scheduling problem with fairness constraints that allows us to find a schedule with maximum aggregate rate that achieves approximately the same fairness as the classic proportional fair scheduler. The results show that, for the problem settings studied, up to around 30% increase in aggregate rate compared to classic proportional fair scheduling (PFS) is possible with no decrease in fairness when blockages can be accurately predicted 0.5 seconds in advance. Furthermore, aggregate rate could be doubled compared to PFS if blockages can be accurately predicted 5 seconds in advance. While these results demonstrate the very promising potential of proactive scheduling, we also discuss several future research directions that must be pursued to effectively realize the approach.

Beam alignment is a critical aspect in millimeter wave (mm-wave) cellular systems. However, the inherent limitations of channel estimation result in beam alignment errors, which degrade the system performance. For systems with a large number of antennas at the base station, downlink channel estimation is performed using uplink pilot signals. The beam alignment errors, thus, depend on the user equipment (UE) transmit power, which needs to be managed properly as the UEs are battery powered. This paper investigates how the use of uplink power control for the transmission of pilot signals in a mm-wave network affects the downlink beam alignment errors, which depend on various link parameters. We use stochastic geometry and statistics of the Student's$t$-distribution to develop an analytical model, which captures the interplay between the uplink power control and downlink signal-to-noise ratio (SNR) coverage probability. Our results indicate that using uplink power control significantly reduces UE power consumption without adversely affecting the downlink SNR coverage.

In this paper, we investigate the optimal line-of-sight (LoS) coverage problem for multiple access point (multi-AP) mmWave wireless LANs in indoor scenarios. Due to the weak diffraction ability of mmWave signals at 60 GHz, maintaining LoS communications between APs and client devices is critical to achieve ultra-high data rates with mmWave communications. We focus on the use of multiple APs deployed to maximize LoS coverage in a target area, and we develop multi-AP placements that maximize LoS coverage by means of both analytical and algorithmic methods. We consider two main scenarios, which differ in their assumptions about knowledge of obstacles and clients. In a random-obstacle, random-client scenario, we derive the LoS-optimal positions of APs by solving a thinnest covering problem. For a fixed-obstacle, random-client scenario, we propose an efficient algorithm that produces a multi-AP placement, which is shown through simulation to provide near-optimal LoS coverage. Finally, through extensive ns-3 simulations based on the IEEE 802.11ad protocol and mmWave-specific channel models, we show that our multi-AP placements are significantly better than existing placement approaches, both in terms of LoS coverage and aggregate throughput.

Malware analysis aims to understand how malicious software carries out actions necessary for a successful attack and identify the possible impacts of the attack. While there has been substantial research focused on malware analysis and it is an important tool for practitioners in industry, the overall malware analysis process used by practitioners has not been studied. As a result, an understanding of common malware analysis workflows and their goals is lacking. A better understanding of these workflows could help identify new research directions that are impactful in practice. In order to better understand malware analysis processes, we present the results of a user study with 21 professional malware analysts with diverse backgrounds who work at 18 different companies. The study focuses on answering three research questions: (1) What are the different objectives of malware analysts in practice?, (2) What comprises a typical professional malware analyst workflow, and (3) When analysts decide to conduct dynamic analysis, what factors do they consider when setting up a dynamic analysis system? Based on participant responses, we propose a taxonomy of malware analysts and identify five common analysis workflows. We also identify challenges that analysts face during the different stages of their workflow. From the results of the study, we propose two potential directions for future research, informed by challenges described by the participants. Finally, we recommend guidelines for developers of malware analysis tools to consider in order to improve the usability of such tools.

Dense deployment of small-cell base stations (BSs) requires a backhaul network to efficiently connect the BSs to the core network. In this paper, we focus on a hybrid backhaul architecture where some BSs connect with fiber to the core network and provide mm Wave backhaul connections for the rest of the BSs. This architecture brings new challenges, e.g., how to prevent a large amount of traffic from becoming concentrated at certain egress BSs, thereby hurting overall backhaul performance. In this paper, we propose a load-balanced routing algorithm to address this challenge. We first define the concept of load balance factor (LBF) and address the challenge through a hill climbing procedure that attempts to minimize LBF. Results show that the proposed algorithm can distribute the dynamic traffic loads from different BSs nearly optimally among fiber-connected BSs for the simulated settings. We also present a variation of the algorithm that permits trade-offs between routing path length and load balance factor.

To accommodate increasingly intensive application bandwidth demands, mmWave WLAN at 60 GHz has been identified as a promising technology with the potential to achieve Gbps throughput. However, mmWave performance is highly dependent on the signal's line-of-sight (LoS) condition due to its high penetration loss when obstructed. We study the use of dedicated flat passive reflectors to improve coverage in indoor mmWave WLANs through a reflector placement scheme that accommodates any general indoor scenario with pre-deployed ceiling-mounted access points (APs). The reflector locations are efficiently selected among all available vertical surfaces within the indoor environment. Through simulations, we show that deployment of intelligently placed reflectors can improve LoS coverage by up to 10%, which is more than deploying one additional AP. Results are provided to illustrate how different factors affect coverage and insights about preferred reflector placements are provided.

While deep learning has brought promising advances to semantic segmentation tasks for autonomous vehicles, the performance strongly depends on the coverage of collected data and the quality of annotations. To overcome the barrier of insufficient high quality training data covering a complex range of vehicular scenarios, in this paper, we propose a multi-view-based active learning framework (MultiVTrain), which enables the vehicles to collaboratively generate training data and accurate labels without querying remote human annotators. As images captured by RGB cameras are vulnerable to occlusion and limited field-of-view, a novel multi-view prediction transfer scheme is introduced to leverage sensor data fusion and transfer predictions of one view to another. This allows information from different views to be aggregated, which improves the quality of the generated annotations. Extensive evaluation results demonstrate that our proposed MultiVTrain framework outperforms other active learning baselines by ∼ 9%, and passive supervised learning baselines trained with ground truth labels by ∼ 2.5%, for the same training set size.

The sensitivity to blockages at millimeter-wave (mm-wave) frequencies is very different from that at sub-6 GHz frequencies. The blockages affect the user-to-base station (BS) associations and the resulting association regions of the BSs in the network. This in turn alters the load, i.e., the total number of users associated to a BS. In this paper, we use a stochastic blockage model to analyze such effects. We characterize the variation in the load as a function of the blockage environment in a stochastic geometric setting. Our analysis indicates that in the extreme cases of total blocking and no blocking, the mean load on the tagged mm-wave BS is identical to that of a sub-6 GHz BS for a given BS and user density. For intermediate blockage environments, the mean load on the tagged mm-wave BS is found to be less than that on a sub-6 GHz BS. Using Monte-Carlo simulations, we establish that the existing analytical models for load characterization in mm-wave networks result in overestimation of the load per BS and underestimation of the achievable rate.

This paper focuses on the problem of finding multiple paths with relay nodes to maximize throughput for ultra-high-rate millimeter wave (mmWave) backhaul networks in urban environments. Relays are selected between a pair of source and destination base stations to form multiple interference-free paths. We first formulate the problem of feasibility of multi-path construction as a constraint satisfaction problem that includes constraints on intra-path and inter-path interference and several other constraints that arise from the problem setting. Based on the derived equations, we transform the multiple paths construction problem into a Boolean satisfiability problem. This problem can then be solved through use of a satisfiability (SAT) solver, which however results in a very high running time for realistic problem sizes. To address this, we propose a heuristic algorithm that runs in a fraction of the time of the SAT solver and finds multiple interference-free paths using a modification of a maximum flow algorithm. Simulation results based on 3-D models of a section of downtown Atlanta show that the heuristic algorithm finds multiple paths in almost all the feasible cases (those where the SAT solver succeeds in finding a solution) and produces paths with higher average throughput than the SAT solver. Furthermore, the heuristic increases throughput by 50-100% in typical cases compared to a single-path solution.

mmWave is emerging as an essential technology for next-generation wireless networks due to its capability of delivering multi-gigabit throughput performance. To achieve such a promising performance in mmWave communications, Line-of-sight (LOS) connectivity is a critical requirement. In this work, we explore the strategy of infrastructure mobility to alter the location of an access point (AP) in order to provide LOS connectivity to stations (STAs) in indoor mmWave WiFi networks. Through both simulation-based and theoretical analyses, we make a detailed case for infrastructure mobility by identifying the impact of AP mobile platforms configurations on network performance and propose a ceiling-mounted mobile (CMM) AP model. Then, we compare the performance of a CMM AP with multiple static APs, and we identify that the throughput and fairness performance of a CMM AP is better than as many as 5 ceiling-mounted static APs.

Millimeter-wave communication is a highly promising technology to deliver multi-gigabit-per-second transmission rates for next-generation wireless LANs (WLANs). To achieve such ultra-high throughput performance in indoor scenarios, line-of-sight (LoS) connectivity becomes a critical requirement. Prior work has proposed access point (AP) mobility as an approach to improve LoS conditions and, thereby, approach optimum mmWave WLAN performance. In this work, we present a comprehensive simulation study of linear AP mobility that investigates various dimensions, including the number of mobile APs, the placement of the mobile AP platforms, and the length of the platforms. The results show how WLAN performance varies across these dimensions and also compares the results against a varying number of static APs to quantity the performance gains achievable from mobility. The results show that even 2 or 3 mobile APs can significantly outperform a much larger number of static APs and that deploying up to 3 mobile APs in a room brings substantial performance gains.

Millimeter-wave wireless LANs are targeted for use with bandwidth-intensive applications such as virtual/augmented reality and real-time high-definition video. To maintain high throughput while addressing mmWave signal blockages, multiple access points (APs) within one room to improve line-of-sight conditions is considered a promising approach. In a scenario with fixed and mobile (human) obstacles, we mathematically analyze LoS blockages produced by mobility, and use the analysis to develop a multi-AP association scheme. Our scheme statically assigns primary and backup APs in order to maximize blockage robustness and perform load balancing among APs. Simulation results show that: 1) our static approach can provide blockage tolerance close to that of an expensive dynamic probing approach while achieving higher throughput, 2) the use of client mobility patterns, if known, can improve our static approach even further, and 3) our approach achieves significantly better fairness and load balancing than existing approaches.

Narrow beamwidth and inaccurate angle-of-arrival (AoA) estimation make perfect beam alignment difficult in millimeter-wave (mm-wave) systems. The extent of beam misalignment depends on the uplink received signal-to-noise ratio (SNR) at a single antenna element of the array. Using stochastic geometry, this paper analyzes and quantifies the loss in downlink SNR coverage probability due to beam misalignment. The standard deviation of the beam alignment error is obtained through the Cramér-Rao lower bound (CRLB) of AoA estimation. The analytical results are verified through Monte-Carlo simulations and it is shown that the beam alignment errors affect the system coverage significantly when the downlink SNR threshold (with array gain) is less than 5 dB. It is also illustrated that increasing the number of antennas alone cannot counter the effects of beam alignment errors.

Software-defined networking (SDN) is fundamentally changing the way networks operate, enabling programmable and flexible network management and configuration. As the de facto standard southbound interface of SDN, OpenFlow defines how the control plane interacts with the data forwarding plane. In OpenFlow, flow tables play a significant role in packet forwarding. However, the size of the flow table is limited due to power, cost, and silicon area constraints and capacity-limited tables cannot hold all of the active flows in medium-to-large-scale SDN networks. Thus, when a flow table reaches capacity, an intelligent eviction strategy, which efficiently manages the limited flow table resource, is critical. In this paper, we propose Smart Table EntRy Eviction for OpenFlow Switches (STEREOS), which uses machine learning to classify flow entries as active or inactive and forms the basis for intelligent eviction. Trace-driven simulations demonstrate that STEREOS increases flow table usage by more than 50% and reduces incorrect flow entry evictions by up to 78%, compared with the dominant Least Recently Used eviction policy. Moreover, packet-level simulations of a datacenter network demonstrate that STEREOS can greatly reduce the control overhead, increase overall network throughput by 19%, and reduce packet loss rate by 70%.

mmWave communication is a highly promising technology for 5G wireless backhaul. However, network performance is hard to predict due to the sensitivity of mmWave signals to blockages. In this paper, we propose an analytical framework to incorporate blockage effects and evaluate blockage robustness within a previously proposed interference-free topology for roadside relay-assisted mmWave backhaul. Through stochastic geometric analysis, the blockage probabilities for four types of blockages identified in prior work are derived as a function of the topology parameters and obstacle density. Analysis of the effect of topology parameters on blockage probability yields insight that leads to a modified topology, which maintains the desirable interference-free property but has better blockage robustness than the original topology. Simulation results demonstrate that the modified topology can maintain very high throughput and has significantly improved robustness as compared to the original topology, while using the same number of relays.

This paper studies how to fairly and efficiently allocate the two limited resources in software-defined data center networks (DCNs), namely the flow table and the control channel bandwidth. The problem considers routing path selection together with allocation of flow table entries and control channel bandwidths. The objective is to maximize the satisfaction ratio for flow groups in the network in terms of the two aforementioned resources, with the routing path optimized and different fairness constraints enforced. Our approach is to aggregate individual flows into flow groups and then find the optimal routing paths and the corresponding resource allocation vectors for each flow group. We study different fairness models in this work and also include a mechanism to relax the fairness constraint, which produces a range of solutions that permits a trade-off between total demand satisfaction and fairness.

Line-of-sight (LOS) is a critical requirement for mmWave communication. In this work, we make the case for a ceilingmounted mobile (CMM) AP by comparing its performance with other types of AP mobility and single static AP. We then present Hawkeye to solve the optimal location discovery problem for a CMM AP using a machine learning (ML) algorithm. Hawkeye relies purely on the connectivity matrix between STAs and the AP to decide if and where the AP should move to for maximizing LOS connectivity. Using a prototype implementation, we show that the throughput of Hawkeye is 219% and 129% compared with single static AP and other approaches for AP mobility, respectively.

mmWave communication has been recognized as a highly promising technology for 5G wireless backhaul, which is capable of providing multi-gigabit per second transmission rates. However, in urban wireless backhaul environments, unforeseen events can cause short-term blockages or node failures and, therefore, network survivability is extremely important. In this paper, we investigate a novel relay-assisted mmWave backhaul network architecture, where a number of small-cell BSs and relays are deployed, e.g. on the lampposts of urban streets. Relays are used to provide multi-hop line-of-sight paths between small-cell BSs, which form logical links of the network. In this scenario, the interconnected logical links make up a mesh network, which offers opportunities for both link-level and network-level reconfiguration. We propose two joint link-network level reconfiguration schemes for recovery after exceptional events. One prioritizes relay path (link-level) reconfiguration and uses alternate network-level paths only if necessary. The other splits traffic on both reconfigured links and backup paths to improve network throughput. Simulation results demonstrate that the proposed schemes significantly outperform purely link-level and purely network-level reconfiguration schemes. The proposed approaches are shown to not only maintain high network throughput but to also provide robust blockage/fault tolerance across a range of scenarios for urban mmWave backhaul networks.

mmWave communication in 60GHz band has been recognized as an emerging technology to support various bandwidth-hungry applications in indoor scenarios. To maintain ultra-high throughputs while addressing potential blockage problems for mmWave signals, maintaining line-of-sight (LoS) communications between client devices and access points (APs) is critical. To maximize LoS communications, one approach is to deploy multiple APs in the same room. In this paper, we investigate the optimal placement of multiple APs using both analytical methods and simulations. Considering the uncertainty of obstacles and clients, we focus on two typical indoor settings: random-obstacle-random-client (RORC) scenarios and fixed-obstacle-random-client (FORC) scenarios. In the first case, we analytically derive the optimal positions of APs by solving a thinnest covering problem. This analytical result is used to show that deploying up to 5 APs in a specific room brings substantial performance gains. For the FORC scenario, we propose the shadowing-elimination search (SES) algorithm based on an analytic model to efficiently determine the placement of APs. We show, through simulations, that with only a few APs, the network can achieve blockage-free operation in the presence of multiple obstacles and also demonstrate that the algorithm produces near-optimal deployments. Finally, we perform ns-3 simulations based on the IEEE 802.11ad protocol at mmWave frequency to validate our analytical results. The ns-3 results show that proposed multi-AP deployments produce significantly higher aggregate performance as compared to other common AP placements in indoor scenarios.

Emerging applications in connected vehicles have tremendous potential for advances in safety, navigation, traffic management and fuel efficiency, while also posing new security challenges such as false information attacks. This paper targets the problem of securing critical information that is disseminated among nearby vehicles for safety and traffic efficiency purposes through distributed consensus. We present a consensus algorithm, which uses a "proof of eligibility" test to establish that a group of vehicles are actually within the vicinity of the information source. With the presence of a limited number of compromised (Byzantine faulty) participants, our algorithm provides correct consensus among healthy vehicles in real time. The algorithm provides fast and reliable consensus group formation and private key distribution without privileged members, trusted setup, or leader election. In addition to proving a safety property of our consensus algorithm, we have implemented it on top of a widely-used vehicle simulation environment (SUMO, OMNeT++ and Veins) and evaluated its performance on a model of the streets in a real midtown area. Simulation results demonstrate that the algorithm can reach consensus very efficiently (within 9.5s) and with up to 30% of compromised vehicles in a given area. The simulations also demonstrate the ability of our algorithm to more quickly disseminate information about a traffic accident and more efficiently route traffic around the accident site, as compared to previous robust information dissemination approaches.

Confidentiality is a fundamental goal in many security contexts. Deception is another goal in which the intention is to mislead adversaries, for example by planting false information in a system. In this paper, we consider an approach that combines confidentiality and deception using secret sharing, which has traditionally been used strictly for confidentiality purposes. The motivation for this is to protect confidentiality as far as possible while acknowledging that no confidentiality scheme provides perfect protection. If confidentiality is breached and information is accessed by unauthorized individuals, our techniques will reveal, with high probability, only false information. This provides deception on top of the confidentiality provided by ordinary secret sharing. We refer to our approach as "deceptive secret sharing" and we present techniques that work with both XOR secret sharing and Shamir's polynomial-based threshold secret sharing. We provide extensive evaluations of both overhead and security of our techniques and we also show how they provide tunable security that can trade off security and overhead by varying a single parameter of the schemes.

In this paper, we consider the multiuser MIMO scheduling problem for dense wireless networks with access point cooperation. The problem is to maximize the aggregate throughput within a single cluster of access points, while maintaining a general fairness criterion. To alleviate the protocol overhead and sustain the performance of both stationary and mobile users, we propose a mobility-aware scheduling approach, which places users into stationary and mobile groups based on a novel CSI similarity metric. The algorithm then schedules the two groups into separate time slots. To balance fairness between stationary and mobile user groups, we adaptively determine their transmission time fractions. Different scheduling strategies are applied for the two groups. For stationary users, we collect CSI infrequently and perform a computationally expensive scheduling algorithm that is highly optimized to maximize throughput while maintaining fairness. For mobile users, we do per-time-slot CSI measurement and schedule users for each time slot using a very fast but less-optimized algorithm. Numerical results demonstrate that, when accounting for CSI feedback and scheduling overheads, our proposed scheduling algorithm with mobility awareness maintains very good fairness and provides substantial performance gains compared to conventional approaches that do not separate mobile and stationary users.

With the advent of 5G, mmWave communications are being investigated for wireless backhaul. The high data rates possible with mmWave are well suited for backhaul networks, while the large number of small cells necessary to support 5G make connecting fiber to every base station difficult and costly. We investigate backhaul topologies deployed along roadsides to provide 5G service to vehicles. The challenge is to achieve the very high data rates necessary to handle backhaul traffic while managing self interference that can occur due to the near- straight-line topology that arises from a roadside deployment. We investigate wireless backhaul networks that use relay nodes and a regular triangular-wave topology to meet the performance objective. The triangular-wave is a regular topology that can be deployed on regularly-spaced lampposts alongside a road. We derive conditions necessary for the triangular-wave topology to be interference-free and throughput-optimal. We also investigate how the proposed topology performs using lamppost positions taken from a 12 km stretch of highway in Atlanta. Results show that the topology can achieve throughputs very close to the ideal case and is capable of supporting backhaul throughputs of 10+ Gbps in real roadside environments.

With the increasing use of bandwidth-hungry applications on mobile devices, mmWave communication is considered a key enabling technology for 5G cellular networks. One very promising use of mmWave communication is in wireless backhaul for 5G. In this paper, we consider wireless backhaul links deployed along the side of a road, which will be a common scenario both in urban environments and on highways. We investigate blockage robustness within an interference-free topology previously proposed for roadside wireless backhaul. Reconfiguration algorithms are provided both for the case where rescheduling is possible after reconfiguration and for the case that the original transmission schedule must be maintained. We prove that our reconfiguration algorithms are guaranteed to maintain connectivity under several obstacle scenarios. We also evaluate the algorithms' performance with varying numbers of randomly-placed obstacles through simulation. Results show that our algorithms not only achieve high throughputs close to the no-blockage case, but also provide high blockage tolerance rates for the common case of a few obstacles along a several hundred meter section of a road.

This paper focuses on the problem of path selection with amplify-and-forward (AF) relays for long-range ultra-high-speed millimeter wave (mmWave) backhaul networks in urban environments. Relays are selected between a pair of source and destination nodes to achieve the highest signal-to-noise ratio (SNR) at the destination. We first derive an equation for the end-to-end SNR of a relay path in a setting that approximates the urban mmWave backhaul environment. Based on the derived equation, we transform the maximum throughput relay selection problem to the shortest path problem in graphs. Dijkstra's algorithm can then be used to find maximum throughput relay paths, which however are shown to require a large number of relays. To address this, we propose a dynamic programming algorithm to find a highest throughput path with a given number of hops. Simulation results based on 3-D models of a section of downtown Atlanta show that these algorithms can be combined to find relay paths with a small number of hops and very high throughput.

To mitigate the co-channel interference across adjacent access points (APs) and break the performance bottleneck in dense wireless networks, multiple APs are expected to share the channel state information and cooperatively process the user signals. While the inter-user interference can be eliminated using Block Diagonalization (BD) precoding technique, the number of simultaneous users is limited by the total number of transmit antennas. In this paper, we propose a novel pairing-and-binary-tree-based user selection algorithm (PBUS) to address the user selection issue for multi-user MIMO in dense environments. With the fitness metric evaluated for each pair of users, a binary tree is constructed to store multiple candidate user groups. The best user group is then selected from these candidates. PBUS can achieve both good sum-rate performance and low computational complexity, and also has the flexibility to trade off sum-rate performance and computational complexity.

While many institutions, whether industrial, academic, or governmental, satisfy their computing needs through public cloud providers, many others still manage their own resources, often as geographically distributed datacenters. Spare capacity from these geographically distributed datacenters could be offered to others, provided there were a mechanism to discover, and then request these resources. Unfortunately, single datacenter administrators tend not to cooperate due to issues of scalability, diverse administrative policies, and site-specific monitoring infrastructure. This paper describes RBAY, an integrated information plane that enables secure and scalable sharing between geographically distributed datacenters. RBAY's key design features are twofold. First, RBAY employs a decentralized `hierarchical aggregation tree' structure to seamlessly aggregate spare resources from geographically distributed datacenters to a global information plane. Second, RBAY attaches to each participating server a `admin-customized' handler, which follows site-specific policy to expose, hide, add, remove resources to RBAY, and thus fulfill the task of `which resource to expose to whom, when, and how'. An experimental evaluation on eight real-world geo-distributed sites demonstrates RBAY's rapid response to composite queries, as well as its extensible, scalable, and lightweight nature.

Millimeter wave (mmWave) communication is a key enabling technology for 5G cellular systems. However, due to mmWave propagation characteristics, link length for very high rates is limited and will likely necessitate the use of relay nodes for longer-range ultra-high-speed backhaul communications. This paper investigates relay selection and scheduling to support high end-to-end throughput in mmWave relay-assisted backhaul networks in urban environments. A major challenge in urban environments is the presence of large obstacles (buildings) that block long line-of-sight paths, which arenecessary for very high capacity mmWave links. Using a 3D model for buildings targeted at urban environments, we provide optimal and efficient algorithms both for scheduling communications along a single mmWave relay-assisted path and for choosing the relay-assisted path with maximum throughput among all candidate paths connecting a given base station pair. In addition to proving optimality of these algorithms, we evaluate their performance through simulations based on a real urban topology. Simulation results show that our algorithms can produce short relay paths with end-to-end throughputs of around 10 Gbps and higher that are capable of providing virtual mmWave links for a wireless backhaul use case. Our algorithms improve throughput from 23% to 49% over a range of settings, as compared to average relay paths, and throughput can be more than doubled compared to some relay path choices with similar numbers of relays.

This paper studies the fair scheduling problem for dense wireless networks with AP cooperation and MIMO links. The problem is to maximize the aggregate throughput while meeting a specified fairness objective. The proposed scheduling algorithm works with a novel single-slot throughput optimization procedure to first generate a set of candidate communication sets that are both high-performing and have good representation among all users. For a given set of candidate communication sets, our algorithm then produces a communication schedule that achieves near-optimal aggregate throughput among solutions that meet the specified fairness objective. Simulation results show that our proposed scheduling algorithm achieves high aggregate throughput while maintaining very good fairness. We also include a mechanism to relax the fairness constraint by a specified amount, which produces a range of solutions that permit a tradeoff between performance and fairness.

This paper addresses the problem of weighted sum rate (WSR) maximization in dense wireless networks with cooperative access points (APs) subject to a per-AP power constraint. We propose a combined optimization procedure that performs both user selection and MIMO weight calculation and scales well as the number of users increases. User selection eliminates some undesirable users, while MIMO weight calculation determines the precoders and combiners for all active nodes. A new performance metric, which takes into account available power, channel quality and orthogonality, and user weights, is used to perform an initial phase of user selection. A WSR maximization algorithm is then executed to optimize MIMO weights of selected users. The proposed algorithm includes additional user selection, i.e. certain users not eliminated in the first phase will be assigned zero-power stream during its execution. Numerical results show that our proposed algorithm achieves about 25% higher aggregate performance than the best existing algorithm while having a substantially lower running time. In fact, the running time is nearly constant as the number of users increases due to the very fast initial user selection phase.

We consider the problem of maximizing performance in multihop wireless networks while achieving fairness among flows. While time-based fairness has been widely recognized as the appropriate fairness mechanism in single-hop wireless networks, no analogous notion has been developed for multihop wireless networks. We define the first general notion of time-based fairness for multihop networks by abstracting a network into a virtual single-hop network and applying the single-hop time-based fairness notion. This produces rate shares for each flow in the network, and we develop a constructive method for achieving these rate shares through physical-interference-aware scheduling. When combined with an appropriate link transmission policy, this scheduling approach preserves the time-based-fair rate shares for flows even with spatial reuse and the resulting rate reductions that occur among concurrent links. To our best knowledge, this is the first constructive approach for achieving fair rate shares in multihop wireless networks with or without interference consideration. We also prove that, with an appropriate scheduling algorithm, this approach produces an aggregate rate that is within a constant factor of the maximum aggregate rate subject to time-based fairness. Finally, we perform extensive simulations, which show that our approach as much as doubles the aggregate rate of a solution that approximates max-min fairness, while achieving a more natural fairness property.

This paper addresses the problem of fair scheduling of MIMO links in dense wireless network deployments where interference suppression is carried out via linear MIMO processing to optimize network performance. We formulate and solve an optimal MIMO link scheduling problem, where the goal is to maximize aggregate throughput while meeting a specified fairness criterion. Evaluations in a modified version of ns-3 show that our MIMO link scheduler more than doubles the performance of 802.11n, while achieving a fairness index of 90-95%.

We propose an algorithm whose goal is to maximize the sum rate of a set of interfering multiple-input multiple-output (MIMO) links by jointly optimizing which subset of transmitters should transmit, the number of streams for each transmitter (if any), and the beamforming and combining weights that support those streams. We present numerical results to illustrate that our algorithm achieves a sum rate higher than previously reported algorithms at high interference, and that it achieves comparable performance to the top-performing algorithms at medium and low interference. In one high-interference example with many links, our algorithm achieves a 65% higher sum rate than previously reported algorithms.

In this paper, we consider how proportional fairness in wireless networks is impacted by spatial reuse and the interference it produces. We observe that, in scenarios where spatial reuse is possible (e.g., in high-density WLAN environments), the classic notion of time-based proportional fairness can be severely impacted: some users might experience very large interference penalties while other users might get larger bandwidth proportions than what they would have received with time-based proportional fairness and no spatial reuse. To account for this, we introduce the concept of interference-aware STDMA time-based proportional fairness (i-STPF), and compare it to ordinary STDMA time-based proportional fairness (STPF). We present an εi-STPF scheduling algorithm, and prove that it approximates the time-based fair bandwidth allocation (up to a small positive constant ε), while providing an aggregate throughput that is within a constant factor from optimal. We also present a heuristic i-STPF scheduling algorithm and compare it through simulation to a similar heuristic STPF scheduler, and to an interference-aware, rate-based scheduler. The results show that the i-STPF scheduler: i) achieves excellent aggregate throughput about 35% higher than rate-based throughput; and ii) maintains a close approximation to time-based fairness without interference.

In this paper, we consider the problem of building mesh-based multicast routing structures that account for the impact of interference in wireless multihop networks. Our analysis is based on the most accurate known interference model, namely the physical interference model. We first analyze interference-aware mesh structures that augment individual paths in a multicast tree. Based on this analysis, we propose two interference-aware multicast mesh routing structures, which extend an interference-aware Steiner multicast tree in two different ways to form interference-aware meshes. We evaluate the performances of our proposed interference-aware multicast mesh structures in wireless networks where wireless links are bursty and nodes can be faulty. Under these conditions, we show that our proposed algorithms provide up to 80% increase in goodput over existing tree-based multicast routing structures and up to 45% increase in goodput over existing mesh-based multicast routing structures.

In this paper, we revisit the problem of optimal tree-based routing structures for multicast in wireless multihop networks, but accounting for the impact of interference. Our analysis is based on the most accurate known interference model, namely the SINR-based physical interference model. We first study the problem in a low-intensity multicast scenario where we derive optimal node selection strategies for different subtree structures. We then extend these analyses to account for interference between consecutive packets in higher-rate multicast scenarios. Based on these analyses, we propose and evaluate two new multicast routing structures: the interference-aware Steiner tree (IAST) algorithm, which requires global knowledge of node locations, and the fixed-distance tree merging (FTM) algorithm, which does not require global knowledge. We show that our proposed algorithms provide up to 57% reduction in schedule length and up to 41% increase in goodput over existing tree-based routing structures.

The problem of multiple-input-multiple-output (MIMO) feasiblity refers to whether it is possible to support specified numbers of streams allocated to the links of an MIMO network while canceling all interference. In unilateral interference cancellation, nodes account only for interfering links that they have been assigned to cancel and ignore other interfering links. We present several different formulations of the unilateral MIMO feasibility problem and use these formulations to analyze the problem's complexity and develop heuristic feasibility algorithms. We first prove that the general unilateral feasibility problem is NP-complete. We then identify several special cases where the problem is solvable in polynomial time. These include when only receiver-side interference cancellation is performed, when all nodes have two antenna elements, and when the maximum degree of the network's interference graph is two. Finally, we present several heuristic feasibility algorithms derived from different problem formulations and evaluate their accuracies on randomly generated MIMO networks.

We propose an algorithm to allocate streams and find the corresponding beamforming and combining weights that maximize the sum rate of a set of interfering multiple-input multiple-output (MIMO) links. Our algorithm iteratively computes the beamforming and combining weights of each link and determines how many streams, if any, are allocated to each link. Assigning zero streams to a link is desirable whenever the interference introduced by activating that link outweighs the throughput contributed by the link. We present numerical results to illustrate that our algorithm achieves a sum rate higher than previously reported algorithms at high interference, and that it achieves similar performance to the top-performing algorithms at medium and low interference. In one high-interference example with many links, our algorithm achieves a 65% higher sum rate than the best-known alternative.

We tackle the problem of determining the beamforming and combining weights in a network of interfering multiple-input multiple-output (MIMO) links. We classify any strategy for computing these weights as either unilateral or bilateral. A unilateral strategy is one for which the responsibility of cancelling interference from one node to another is preassigned to lie solely with only one of the two nodes, so that the other node is free to ignore the interference. Many existing strategies for managing interference in a network of MIMO nodes adopt the unilateral approach. In contrast, a bilateral strategy is one for which the responsibility of cancelling interference from one node to another is not preassigned, but is instead shared by both sides as the weights are computed. We present numerical examples to illustrate that bilateral strategies can significantly outperform unilateral strategies, especially for large networks and high interference. In one example, a bilateral approach delivers an aggregate capacity that is 227% higher than that of the best unilateral approach. We conclude that, although unilateral strategies are useful for determining whether or not the streams allocated in a network of MIMO links can coexist, the weight computation should be done bilaterally to prevent throughput loss.

The values of data elements stored in biomedical databases often draw from biomedical ontologies. Authorization rules can be defined on these ontologies to control access to sensitive and private data elements in such databases. Authorization rules may be specified by different authorities at different times for various purposes. Since such policy rules can conflict with each other, access to sensitive information may inadvertently be allowed. Another problem in biomedical data protection is inference attacks, in which a user who has legitimate access to some data elements is able to infer information related to other data elements. We propose and evaluate two strategies; one for detecting policy inconsistencies to avoid potential inference attacks and the other for detecting policy conflicts.

A MIMO network is a wireless network made up of individual MIMO links. The problem we consider is to maximize throughput in a multihop MIMO network with interference suppression. Our problem formulation accounts for variable rates on the MIMO links, which depend on the channel conditions of the link, and the manner in which the diversity-multiplexing trade-off is handled. We present an ILP formulation of the MIMO one-shot scheduling problem with variable rates, which is the first exact formulation of a MIMO network optimization problem that accounts for full interference suppression capabilities of MIMO links. We use CPLEX to evaluate the optimal solution based on the ILP formulation for wireless networks with up to 32 concurrently transmitting links. We also modify a heuristic algorithm from a related MIMO scheduling problem to work in our problem setting. Results show that the heuristic can scale to networks with 80 or more concurrent links, but is 10-20% from optimal in terms of throughput. We show that the heuristic scheduler is not able to fully exploit the diversity-multiplexing-interference suppression tradeoff, which is inherent in the problem. This shows that there is substantial room for developing improved scheduling algorithms for MIMO networks and provides some insight into promising directions to explore.

Distributed hash tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We address both of these problems through replica placement. We characterize tree-based routing DHTs and define MaxDisjoint, a replica placement that creates route diversity for these DHTs. We prove that this placement creates disjoint routes and find the replication degree necessary to produce a desired number of disjoint routes. Using simulations of Pastry (a tree-based routing DHT), we evaluate the impact of MaxDisjoint on routing robustness compared to other placements when nodes are compromised at random or in a contiguous run. Furthermore, we consider another route diversity mechanism that we call neighbor set routing and show that, when used with our replica placement, it can successfully route messages to a correct replica even with a quarter of the nodes in the system compromised at random. Finally, we demonstrate a family of replica query strategies that can trade off response time and system load. We present a hybrid query strategy that keeps response time low without producing too high a load.

In this paper, we consider the classical problem of link scheduling in wireless networks under an accurate interference model, in which correct packet reception at a receiver node depends on the signa-to-interference-plus-noise ratio (SINR). While most previous work on wireless networks has addressed the scheduling problem using simplistic graph-based or distance-based interference models, a few recent papers have investigated scheduling with SINR-based interference models. However, these papers have either used approximations to the SINR model or have ignored important aspects of the problem. We study the problem of wireless link scheduling under the exact SINR model and present the first known true approximation algorithms for transmission scheduling under the exact model. We also introduce an algorithm with a proven approximation bound with respect to the length of the optimal schedule under primary interference. As an aside, our study identifies a class of “difficult to schedule” links, which hinder the derivation of tighter approximation bounds. Furthermore, we characterize conditions under which scheduling under SINR-based interference is within a constant factor from optimal under primary interference, which implies that secondary interference only degrades performance by a constant factor in these situations.

It is common practice in wireless multihop network evaluations to ignore interfering signals below a certain signal strength threshold. This paper investigates the thesis that this produces highly inaccurate evaluations in many cases. We start by defining a bounded version of the physical interference model, in which interference generated by transmitters located beyond a certain distance s from a receiver is ignored. We then derive a lower bound on neglected interference and show that it is approximately two orders of magnitude greater than the noise floor for typical parameter values and a surprisingly small number of nodes. We next evaluate the effect of neglected interference through extensive simulations done with a widely-used packet-level simulator (GTNetS), considering 802.11 MAC with both CBR and TCP traffic in networks of varying size and topology. The results of these simulations show very large evaluation errors when neglecting far-away interference: errors in evaluating aggregate throughput when using the default interference model reached up to 210% with 100 nodes, and errors in individual flow throughput were far greater.

This paper considers the problem of scheduling the maximum number of streams in a single time slot under the MIMO degrees of freedom (DOF) model, when all links are in a single collision domain. In the DOF model, nodes can use degrees of freedom provided by their antenna arrays to multiplex multiple streams on a single link and/or cancel interference between concurrently transmitting links. Given a set of links with data to transmit that are free of primary interference, we provide optimal constructions for both the case where only spatial reuse (from interference cancellation) is allowed and the case where both spatial reuse and spatial multiplexing can be done simultaneously. Our analysis allows deriving clean throughput performance trends when the number of available DOFs is arbitrarily increased. These trends show that combining spatial multiplexing with spatial reuse can arbitrarily increase throughput compared to spatial reuse only, and that close to two-fold throughput increases can be achieved compared to spatial multiplexing only. Finally, we show how the approach can be extended to deal with primary interference and optimally solve the one-shot stream scheduling problem for an arbitrary set of MIMO links in a single collision domain.

It is known that CSMA/CA channel access schemes are not well suited to meet the high traffic demand of wireless mesh networks. One possible way to increase traffic carrying capacity is to use a spatial TDMA (STDMA) approach in conjunction with the physical interference model, which allows more aggressive scheduling than the protocol interference model on which CSMA/CA is based. While an efficient centralized solution for STDMA with physical interference has been recently proposed, no satisfactory distributed approaches have been introduced so far. In this paper, we first prove that no localized distributed algorithm can solve the problem of building a feasible schedule under the physical interference model. Motivated by this, we design a global primitive, called SCREAM, which is used to verify the feasibility of a schedule during an iterative distributed scheduling procedure. Based on this primitive, we present two distributed protocols for efficient, distributed scheduling under the physical interference model, and we prove an approximation bound for one of the protocols. We also present extensive packet-level simulation results, which show that our protocols achieve schedule lengths very close to those of the centralized algorithm and have running times that are practical for mesh networks.

Recently, interest has arisen in use of realistic interference models for transmission scheduling in wireless multihop networks, particularly in mesh networks where throughput is a major concern. In this work, we use the SINR-based physical interference model and develop a uniform framework for transmission scheduling when diverse wireless resources can be exploited. The factors considered are multiple (possibly overlapped) channels, directional antennas, and transmit power control. We develop an efficient heuristic for computing a diversity exploiting schedule based on a new network saturation metric. We prove that, under uniform random node distributions, the schedule produced by our heuristic is within a poly-log factor from optimal with a probability that approaches one as network size increases. Through simulation, we demonstrate the ability of our algorithm to achieve up to a 10-fold throughput improvement with respect to networks without diversity. Our analysis also reveals a number of insights on the ability of diversity exploitation to reduce or eliminate interference.

To enable a rich attribute-based authorization system, it is desirable that a large number of user attributes are available, possibly provided by multiple entities. The user may be required to aggregate his attributes and present them to a service provider to prove he has the right to access some service. In this paper, we present AttributeTrust - a policy-based privacy enhanced framework for aggregating user attributes and evaluating confidence in these attributes. We envision a future where attribute providers will be commonplace and service providers will face the problem of choosing one among multiple attribute providers that can provide the same user attribute. In AttributeTrust, we address this problem by means of a reputation system model based on transitive trust. Entities express confidence in other entities to supply trusted attributes, forming chains from a service provider to different attribute providers. A service provider uses this transitive reputation to decide whether to accept a particular attribute from a specific attribute provider.We discuss how the AttributeTrust model prevents common attacks on reputation systems. AttributeTrust differs from the current approaches by deriving its attack resistance from its specific context of attribute provisioning, its voting mechanism formulation, and unique properties of its confidence relationships.

Privacy is defined as the freedom from unauthorised intrusion. The availability of public records along with intelligent search engines and data mining tools allow easy access to useful information. They also serve as a haven for individuals with malicious intent. This paper proposes an approach that protects the privacy of individual records while retaining the information content. The techniques that have been proposed for privacy protection so far either provide insufficient privacy or too much useful information on account of privacy protection. This paper proposes an attack model to analyse the different types of privacy breaches, proposes a set of properties for good privacy protection, proposes a robust data protection technique, and compares the privacy and usability properties of the new technique with some of the existing techniques.

Anticipating user mobility can be a critical feature for today's mobile systems. We introduce a novel location predictor which incorporates knowledge of a user's potential future locations to improve prediction accuracy. Such future knowledge is often available through contextual sources such as a user's calendar, e-mail, or instant messaging conversations. Simulation results show that our future knowledge leveraging location predictor can improve prediction accuracy by 3% to 95% over history-only Markov predictors, depending on the amount of future knowledge that is available and the type of mobility exhibited by users.

Despite many improvements on original unstructured P2P networks, these systems still suffer from many problems, the most important of which are, (a) lack of guarantees on the integrity of the network topology in the face of churns, (b) excessive traffic cost, and (c) poor quality of search results. This paper introduces an end-to-end scalable unstructured P2P networking solution called SUPNET to address many of these issues. The solution consists of two sub-protocols, SUPNET-T and SUPNET-S, which are, respectively, responsible for network management and search. We investigate the end-to-end performance of our solution, both analytically and empirically. SUPNET-T is a scalable, highly robust protocol, capable of utilizing the heterogenous distribution of network resources. The high stability of SUPNET-T is the result of implementation of a novel distributed feedback mechanism. SUPNET-S, on the other hand, is capable of locating every item, even if a single copy of that item exists in the network. SUPNET-S does this while producing a traffic that scales provably sub-linear with the network size. The protocol also contains mechanisms for efficient search of popular items as well as distributed tuning algorithms. All this, along with a relative ease of implementation and a solid analytical foundation, make SUPNET a compelling solution for unstructured P2P networking.

Wireless mesh networks are expected to be widely used to provide Internet access in the near future. In order to fulfill the expectations, these networks should provide high throughput simultaneously to many users. Recent research has indicated that, due to its conservative CSMA/CA channel access scheme and RTS/CTS mechanism, 802.11 is not suitable to achieve this goal.In this paper, we investigate throughput improvements achievable by replacing CSMA/CA with an STDMA scheme where transmissions are scheduled according to the physical interference model. To this end, we present a computationally efficient heuristic for computing a feasible schedule under the physical interference model and we prove, under uniform random node distribution, an approximation factor for the length of this schedule relative to the shortest schedule possible with physical interference. This represents the first known polynomial-time algorithm for this problem with a proven approximation factor.We also evaluate the throughput and execution time of this algorithm on representative wireless mesh network scenarios through packet-level simulations. The results show that throughput with STDMA and physical-interference-based scheduling can be up to three times higher than 802.11 for the parameter values simulated. The results also show that our scheduling algorithm can schedule networks with 2000 nodes in about 2.5 minutes.

To achieve higher efficiency over their unstructured counterparts, structured peer-to-peer systems hold each node responsible for serving a specified set of keys and correctly routing lookups. Unfortunately, malicious participants can abuse these responsibilities to deny access to a set of keys or misroute lookups. We look to address both of these problems through replica placement. Using Chord as an example, we present an equally-spaced replication scheme and prove that it can be tuned to produce any desired number of disjoint routes. To be specific, we prove that d disjoint routes can be produced by placing 2d-1replicas around a fully populated Chord ring in an equally-spaced fashion. In this situation, we also prove that there exists a route to at least one replica, which contains only uncompromised nodes, even if an attacker controls more than a quarter of the contiguous identifier space in the system. Simulation experiments demonstrate that this scheme performs better than previously proposed replica placement schemes in rings that are sparsely populated, populated in clusters, or populated partially by compromised nodes

Topology control, wherein nodes adjust their transmission ranges to conserve energy and reduce interference, is an important feature in wireless ad hoc networks. Contrary to most of the literature on topology control which focuses on reducing energy consumption, in this paper we tackle the topology control problem with the goal of limiting interference as much as possible, while keeping the communication graph connected with high probability. Our approach is based on the principle of maintaining the number of physical neighbors of every node equal to or slightly below a specific value k. As we will discuss in this paper, having a nontrivially bounded physical node degree allows a network topology with bounded interference to be generated. The proposed approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability both theoretically and through simulation. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that uses distance estimation. k-Neigh guarantees logarithmically bounded physical degree at every node, is the most efficient known protocol (requiring 2n messages in total, where n is the number of nodes in the network), and relies on simpler assumptions than existing protocols. Furthermore, we verify through simulation that the network topologies produced by k-Neigh show good performance in terms of node energy consumption and expected interference.

In a previous paper P. Santi and D. Blough (see ibid., vol.2, no.1, p.25-39, Jan.-Mar. 2003) presented a number of results concerning the asymptotic connectivity of wireless ad hoc networks. This comment includes fixes to several of that paper's results.

Radio configuration (R-CFG) files for software defined radio (SDR) devices can he downloaded over the air, allowing these devices to support multi-mode functionality using a single transceiver. The drawback of this is that the wireless link is constrained and downloading the entire R-CFG could take some time. In an effort to achieve efficiency, this paper presents a new algorithm for differential download, referred to as light differential download algorithm (LDDA). The LDDA is the first differential download algorithm specifically designed for SDR devices. It presents several new features that make not only R-CFG differential download a possibility, but also allows the update of any software by differential download. Experiments using Java 2 Micro Edition are performed to demonstrate the feasibility and superior performance of the LDDA when compared with other approaches.

A sensor network consists of a set of battery-powered nodes, which collaborate to perform sensing tasks in a given environment. It may contain one or more base stations to collect sensed data and possibly relay it to a central processing and storage system. These networks are characterized by scarcity of resources, in particular the available energy. We present a distributed algorithm to solve the unique ID assignment problem. The proposed solution starts by assigning long unique IDs and organizing nodes in a tree structure. This tree structure is used to compute the size of the network. Then, unique IDs are assigned using the minimum number of bytes. Globally unique IDs are useful in providing many network functions, e.g. configuration, monitoring of individual nodes, and various security mechanisms. Theoretical and simulation analysis of the proposed solution have been preformed. The results demonstrate that a high percentage of nodes (more than 99%) are assigned globally unique IDs at the termination of the algorithm when the algorithm parameters are set properly. Furthermore, the algorithm terminates in a relatively short time that scales well with the network size. For example, the algorithm terminates in about 5 minutes for a network of 1,000 nodes

Topology Control (TC) is a well-studied technique used in wireless ad hoc networks to find energy-efficient and/or low-interference subgraphs of the maxpower communication graph. However, existing work has the following limitations: (1) the energy model adopted is quite unrealistic - only transmit power is often considered and homogeneous decay of the radio signal with distance is assumed; (2) the interference measure does not account for multi-hop communications. In this paper, we show the dramatic effect of the underlying energy and interference model on TC. In particular, we demonstrate that by using more realistic energy models and considering the effects of multi-hop interference, radically different conclusions about TC can be drawn; namely that (1) energy efficient TC is essentially meaningless, since every link turns out to be "efficient", and that (2) topologies identified as "interference-optimal" in the current literature can be extremely bad from the viewpoint of multi-hop interference. Given these observations, we propose a new measure of link interference, extend it to deal with multi-hop interference, and design a corresponding optimal communication subgraph, called ATASP. We prove that, in the worst case, ATASP coincides with the maxpower communication graph, showing that in some unfortunate situations also performing multi-hop interference-based TC is pointless. However, the simulation results with random node deployments presented in this paper show that, on the average, ATASP is a sparse subgraph of the maxpower communication graph, and multi-hop interference-based TC is indeed possible. Since computing ATASP requires global knowledge, we experiment through simulation with known localized algorithms for energy-efficient TC and show that they perform well (on the average) with respect to multi-hop interference.

Quorum protocols offer several benefits when used to maintain replicated data but techniques for reducing overheads associated with them have not been explored in detail. It is desirable that a system be able to adapt its operation so that fault tolerance related overheads are only incurred when the protocol execution actually encounters faults. There are a number of issues that need to be carefully examined to achieve such agility of quorum based systems. We make use of a file system prototype, developed in our Agile Store project, to experimentally evaluate several techniques that are important for efficient implementation of Byzantine fault-tolerant quorum protocols. We present an optimistic quorum collection scheme and a probabilistic hashing scheme for determining the response to a quorum request, and show that they lead to significant performance improvements. The Agile Store also makes use of reconfigurable quorum techniques to allow system size and fault threshold to be dynamically varied when, for example, faulty servers are removed, new servers are added, or the threat level is changed. We quantify the performance gains made possible by such reconfiguration of quorum parameters. We also show how performance scales with different system parameters and how it is affected by design choices such as whether to use proxies. We believe that the results in the paper provide important insights into how to implement quorum protocols to provide good performance while achieving Byzantine fault tolerance.

In embedded system-on-a-chip (SoC) applications, the demand for integrating heterogeneous processors onto a single chip is increasing. An important issue in integrating multiple heterogeneous processors on the same chip is to maintain the coherence of their data caches. In this paper, we propose a hardware/software methodology to make caches coherent in heterogeneous multiprocessor platforms with shared memory. Our approach works with any combination of processors that support invalidation-based protocols. As shown in our experiments, up to 58% performance improvement can be achieved with low miss penalty at the expense of adding simple hardware, compared to a pure software solution. Speedup can be improved even further as the miss penalty increases. In addition, our approach provides embedded system programmers a transparent view of shared data, removing the burden of software synchronization.

In a network with quality of service (QoS) support, pricing is an effective means of dealing with congestion control and revenue generation. In the Internet, the needs of the customers and their applications are constantly evolving. An auction based algorithm is the best choice for this environment because it needs minimal a priori information. In this paper, we propose an auction based pricing algorithm which lets customers choose the price as well as the services required, and in which the service provider decides on the admission price threshold and the service level of the differentiated service provided. We then investigate the system's adaptive behavior by simulating it in various environments and situations.

The problem of distributed diagnosis in the presence of dynamic failures and repairs is considered. To address this problem, the notion of bounded correctness is defined. Bounded correctness is made up of three properties: bounded diagnostic latency, which ensures that information about state changes of nodes in the system reaches working nodes with a bounded delay, bounded start-up time, which guarantees that working nodes determine valid states for every other node in the system within bounded time after their recovery, and accuracy, which ensures that no spurious events are recorded by working nodes. It is shown that, in order to achieve bounded correctness, the rate at which nodes fail and are repaired must be limited. This requirement is quantified by defining a minimum state holding time in the system. Algorithm heartbeatcomplete is presented and it is proven that this algorithm achieves bounded correctness in fully-connected systems while simultaneously minimizing diagnostic latency, start-up time, and state holding time. A diagnosis algorithm for arbitrary topologies, known as algorithm forwardheartbeat, is also presented. Forwardheartbeat is shown to produce significantly shorter latency and state holding time than prior algorithms, which focused primarily on minimizing the number of tests at the expense of latency.

We use pricing as an effective strategy to allocate network resources in an efficient way so as to maximize a service provider's revenue. Among all static and dynamic pricing strategies, an auction approach is a widely proposed decentralized mechanism. We propose a scenario where all clients can bid for their required bandwidth as well as the price they are willing to pay. The service provider decides on the admission price and differentiated service provided for each class. These thresholds also provide a future reference for admitting new flows later.

We propose an approach to topology control based on the principle of maintaining the number of neighbors of every node equal to or slightly below a specific value k. The approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that follows the above approach and uses distance estimation. We prove that k-Neigh terminates at every node after a total of 2n messages have been exchanged (with n nodes in the network) and within strictly bounded time. Finally, we present simulations results which show that our approach is about 20% more energy-efficient than a widely-studied existing protocol.

Quorum-based protocols can be used to manage data when it is replicated at multiple server nodes to improve availability and performance. If some server nodes can be compromised by a malicious adversary, Byzantine quorums must be used to ensure correct access to replicated data. This paper introduces reconfigurable Byzantine quorums, which allow various quorum protocol parameters to be adapted based on the behavior of compromised nodes and the performance needs of the system. We present a protocol that generalizes dynamic Byzantine quorums by allowing the system size to change as faulty servers are removed from the system, in addition to adapting the fault threshold. A new architecture and algorithm that provide the capability to detect and remove faulty servers are also described. Finally, simulation results are presented that demonstrate the benefits offered by our approach.

We analyze the critical transmitting range for connectivity in wireless ad hoc networks. More specifically, we consider the following problem: assume n nodes, each capable of communicating with nodes within a radius of r, are randomly and uniformly distributed in a d-dimensional region with a side of length l; how large must the transmitting range r be to ensure that the resulting network is connected with high probability? First, we consider this problem for stationary networks, and we provide tight upper and lower bounds on the critical transmitting range for one-dimensional networks and nontight bounds for two and three-dimensional networks. Due to the presence of the geometric parameter l in the model, our results can be applied to dense as well as sparse ad hoc networks, contrary to existing theoretical results that apply only to dense networks. We also investigate several related questions through extensive simulations. First, we evaluate the relationship between the critical transmitting range and the minimum transmitting range that ensures formation of a connected component containing a large fraction (e.g., 90 percent) of the nodes. Then, we consider the mobile version of the problem, in which nodes are allowed to move during a time interval and the value of r ensuring connectedness for a given fraction of the interval must be determined. These results yield insight into how mobility affects connectivity and they also reveal useful trade offs between communication capability and energy consumption.

We consider the following problem for wireless ad hoc networks: assume n nodes, each capable of communicating with nodes within a radius of r, are distributed in a d-dimensional region of side l; how large must the transmitting range r be to ensure that the resulting network is connected? We also consider the mobile version of the problem, in which nodes are allowed to move during a time interval and the value of r ensuring connectedness for a given fraction of the interval must be determined. For the stationary case, we give tight bounds on the relative magnitude of r, n and l yielding a connected graph with high probability in l-dimensional networks, thus solving an open problem. The mobile version of the problem when d=2 is investigated through extensive simulations, which give insight on how mobility affects connectivity and reveal a useful trade-off between communication capability and energy consumption.

Cooperative cell-based strategies have been recently proposed as a technique for extending the lifetime of wireless ad hoc networks, while only slightly impacting network performance. The effectiveness of this approach depends heavily on the node density: the higher it is, the more consistent energy savings can potentially be achieved. However, no general analyses of network lifetime have been done either for a base network (one without any energy conservation technique) or for one using cooperative energy conservation strategies. In this paper, we investigate the lifetime/density tradeoff under the hypothesis that nodes are distributed uniformly at random in a given region, and that the traffic is evenly distributed across the network. We also analyze the case where the node density is just sufficient to ensure that the network is connected with high probability. This analysis, which is supported by the results of extensive simulations, shows that even in this low density scenario, cell-based strategies can significantly extend network lifetime.

In this paper, we analyze the node spatial distribution of mobile wireless ad hoc networks. Characterizing this distribution is of fundamental importance in the analysis of many relevant properties of mobile ad hoc networks, such as connectivity, average route length, and network capacity. In particular, we have investigated under what conditions the node spatial distribution resulting after a large number of mobility steps resembles the uniform distribution. This is motivated by the fact that the existing theoretical results concerning mobile ad hoc networks are based on this assumption.

In this paper we consider the following problem for ad hoc networks: assume that n nodes are distributed in a d-dimensional region, with 1≤d≤3, and assume that all the nodes have the same transmitting range r; how large must r be to ensure that the resulting network is strongly connected? We study this problem by means of a probabilistic approach, and we establish lower and upper bounds on the probability of connectedness. For the one-dimensional case, these bounds allow us to determine a suitable magnitude of r for a given number of nodes and displacement region size. In an alternate formulation, the bounds allow us to calculate how many nodes must be distributed should the transmitting range be fixed. Finally, we investigate the required magnitude of r in the two- and three-dimensional cases through simulation. Based on the bounds provided and on the simulation analysis, we conclude that, as compared to the deterministic case, a probabilistic solution to this range assignment problem achieves substantial energy savings. A number of other potential uses for our analyses are discussed as well

Parallel computing is seeing increasing use in critical applications. The need therefore arises to test the robustness of parallel applications in the presence of exceptional conditions, or faults. Communication-software-based fault injection is an extremely flexible approach to robustness testing in message-passing parallel computers. A fault injection methodology and tool that use this approach are presented. The tool, known as FIMD-MPI, allows injection of faults into MPI-based applications. The structure and operation of FIMD-MPI are described and the use of the tool is illustrated on an example fault-tolerant MPI application.

Systems with global spares, in which a spare can replace any of multiple identical primary modules, are widely used. We present efficient algorithms for approximating the probability distribution of performance level (number of working modules) in systems with global spares and arbitrary module failure distribution. For nondegradable systems with global spares and arbitrary module failure distribution, our algorithms provide the first efficient solution for reliability. For degradable systems with global spares, our algorithms can be used to produce upper and lower bounds on various dependability measures.

This paper describes a new comparison-based model for distributed fault diagnosis in multicomputer systems with a weak reliable broadcast capability. The classical problems of diagnosability and diagnosis are both considered under this broadcast comparison model. A characterization of diagnosable systems is given, which leads to a polynomial-time diagnosability algorithm. A polynomial-time diagnosis algorithm for t-diagnosable systems is also given. A variation of this algorithm, which allows dynamic fault occurrence and incomplete diagnostic information, has been implemented in the COmmon Spaceborne Multicomputer Operating System (COSMOS). Results produced using a simulator for the JPL MAX multicomputer system running COSMOS show that the algorithm diagnoses all fault situations with low latency and very little overhead. These simulations demonstrate the practicality of the proposed diagnosis model and algorithm for multicomputer systems having weak reliable broadcast. This includes systems with fault-tolerant hardware for broadcast, as well as those where reliable broadcast is implemented in software.

Two algorithms that combine the operations of scheduling and recovery-point insertion for high-level synthesis of recoverable microarchitectures are presented. The first uses a prioritized cost function in which functional unit (FU) cost is minimized first and register cost second. The second algorithm minimizes a weighted sum of FU and register costs. Both algorithms are optimal according to their respective cost functions and require less than 10 min of central processing unit (CPU) time on widely used high-level synthesis benchmarks. The best previous result reported several hours of CPU time for some of the same benchmarks on a computer of similar computational power.

A tree-based fault-tolerant multicast algorithm built on top of pipelined circuit switching is presented. The algorithm is provably deadlock-free and livelock-free, requires only a single message startup, and guarantees messages are delivered over shortest paths in the fault-free and traffic-free case. Simulation results in two-dimensional mesh networks show that the algorithm produces significantly shorter average communication latency than previous fault-tolerant multicast algorithms over a range of network loads and fault conditions.

We present a new approach for fault-tolerant internal clock synchronization in multicomputer systems employing not completely connected networks (NCCNs). The approach is referred to as multistep interactive convergence and is locally implemented in each multicomputer node by a time server process (TSP). We describe a specific algorithm that uses multistep interactive convergence and bases its operation on a logical mapping of the system's TSPs into an m-dimensional array. A TSP executes m steps per round of synchronization, with each step including a call to an interactive convergence procedure. For any TSP, clock readings in step i are gathered only from TSPs with which it shares a row along dimension i of the array. Hence, a TSP reads clocks only from a small subset of the TSPs in the system, which reduces the number of messages by orders of magnitude over a conventional interactive convergence algorithm in which reliable all-to-all broadcast of clock values is done. The algorithm can be used in systems of arbitrary topology and provides the added benefit of increased locality of communication in regular NCCNs such as hypercubes and tori. These advantages can be combined with a variety of message staggering mechanisms to maintain network contention at a minimum. We present expressions for the maximum clock skew, maximum clock drift, maximum clock discontinuity, and number of messages produced by the algorithm, and show that it tolerates arbitrary faults. A comparison with other algorithms that elucidates the advantages of multistep interactive convergence is also provided.

In this paper, we show that for images corrupted by white Gaussian noise, a minimum signal-to-noise ratio (SNR) can be guaranteed in the IDS reconstructed image by adjusting the spread factor of the IDS filter. This can be done with better SNR at low intensities, and less blur at high intensities than for a comparable linear-shift-invariant (LSI) Gaussian filter.

This paper considers the problem of automatic insertion of recovery points in recoverable microarchitectures. Previous work on this problem provided heuristic nonoptimal algorithms that attempted either to minimize computation time with a bounded hardware overhead or to minimize hardware overhead with a bounded computation time. In this paper, we present polynomial-time algorithms that provide provably optimal solutions for both of these formulations of the problem. These algorithms take as their input a scheduled control-data flow graph describing the behavior of the system, and they output either a minimum time or a minimum cost set of recovery point locations. We demonstrate the performance of our algorithms using some well-known benchmark control-data flow graphs. Over all parameter values for each of these benchmarks, our optimal algorithms are shown to perform as well as, and in many cases better than, the previously proposed heuristics.

We present a fault-tolerant algorithm that internally synchronizes clocks in multicomputer systems employing not completely connected networks (NCCNs). The algorithm is referred to as multistep interactive convergence, and is locally implemented in each node by a time sewer process (TSP). The algorithm proceeds in rounds, and bases its operation on a logical mapping of the system's TSPs into an m-dimensional array. A TSP executes m steps per round, each step including a call to an interactive convergence procedure. Clock readings in step i are gathered only from TSPs sharing a row along dimension i of the array, which reduces the number of messages by orders of magnitude over a conventional interactive convergence algorithm. The algorithm can be used in systems of arbitrary topology, and provides the added benefit of increased locality of communication in regular NCCNs. These advantages can be combined with a variety of message staggering mechanisms to maintain network contention at a minimum. We characterize the maximum clock skew maximum clock drift, maximum clock discontinuity, and number of messages produced by the algorithm, and show that it tolerates arbitrary faults. A comparison with other algorithms is provided.

Reconfiguration of memory arrays using spare rows and columns is useful for yield-enhancement of memories. This paper presents a reconfiguration algorithm (QRCF) for memories that contain clustered faults. QRCF operates in a branch and bound fashion similar to known optimal algorithms that require exponential time. However, QRCF repairs faults in clusters rather than individually. Since many faults are repaired simultaneously, the execution-time of QRCF does not become prohibitive even for large memories containing many faults. The performance of QRCF is evaluated under a probabilistic model for clustered faults in a memory array. For a special case of the fault model, QRCF solves the reconfiguration problem exactly in polynomial time. In the general case, QRCF produces an optimal solution with high probability. The algorithm is also evaluated through simulation. The performance and execution-time of QRCF on arrays containing clustered faults are compared with other approximation algorithms and with an optimal algorithm. The simulation results show that QRCF outperforms previous approximation algorithms by a wide margin and performs nearly as well as the optimal algorithm with an execution-time that is orders of magnitude less.

Algorithm-based fault tolerance has been proposed as a technique to detect incorrect computations in multiprocessor systems. In algorithm-based fault tolerance, processors produce data elements that are checked by concurrent error detection mechanisms. We investigate the efficacy of this approach for diagnosis of processor faults. Because checks are performed on data elements, the problem of location of data errors must first be solved. We propose a probabilistic model for the faults and errors in a multiprocessor system and use it to evaluate the probabilities of correct error location and fault diagnosis. We investigate the number of checks that are necessary to guarantee error location with high probability. We also give specific check assignments that accomplish this goal. We then consider the problem of fault diagnosis when the locations of erroneous data elements are known. Previous work on fault diagnosis required that the data sets produced by different processors be disjoint. We show, for the first time, that fault diagnosis is possible with high probability, even in systems where processors combine to produce individual data elements.>

Abstract We consider the problem of efficient information exchange in a communication network whose nodes and/or links are subject to Byzantine faults that are randomly and independently distributed through the network. The goal is almost safe communication, i.e., getting to every fault‐free node information about every other fault‐free node, with probability converging to one as the number of nodes grows. We present nonadaptive almost‐safe communication schemes working for various networks in asymptotically optimal time and using an asymptotically optimal number of message bits.

Diagnosis of multiprocessor systems in which faulty processors can be replaced by spares or repaired is known as sequential diagnosis. A generalization is considered of classical sequential diagnosis, referred to as diagnosis and repair, under a probabilistic model for the faults and test outcomes in a system. It is shown that correct diagnosis and repair of all faulty processors can be achieved with high probability in a large class of systems including, for example, rings, grids, meshes, tori, and hypercubes. These results show, without restrictive assumptions on the behavior of faulty processors, that correct diagnosis can be achieved in these widely used, low-degree systems when a fixed percentage of the processors in the system are faulty.>

Reconfiguration of memory array using spare rows and spare columns, which has been shown to be a useful technique for yield enhancement of memories, is considered. A clustered failure model that adopts the center-satellite approach of F.J. Meyer and D.K. Pradhan (1989) is proposed and utilized to show that the total number of faulty cells that can be tolerated when clustering occurs is larger than when faults are independent. It is also shown that an optimal solution to the reconfiguration problem can be found in polynomial time for a special case of the clustering model. An efficient approximation algorithm is given for the general case of the probabilistic model assumed. It is shown, through simulation, that the computation time required by this algorithm to repair large arrays containing a significant number of clustered faults is small.>

Communications protocols for not-completely-connected networks are presented, and their cost is evaluated in terms of message exchanges. An efficient protocol tailored to convergence function clock synchronization is introduced. The number of messages used by this approach is equal to a proven lower bound on the number of messages and, hence, the approach is optimal. This protocol can be combined with a convergence function algorithm to achieve fault-tolerant clock synchronization in not-completely-connected networks at a far lower cost than previous approaches.>

The authors consider a comparison-based probabilistic model for multiprocessor fault diagnosis. They study the problem of optimal diagnosis, which is to correctly identify the status (faulty/fault-free) of units in the system, with maximum probability. For some parameter values, this probabilistic model is well approximated by the asymmetric comparison model introduced by M. Malek (1980). For arbitrary systems it is shown that optimal diagnosis in the probabilistic model and in Malek's model is NP-hard. However, the authors construct efficient diagnosis algorithms in the asymmetric comparison model for a class of systems corresponding to bipartite graphs which includes hypercubes, grids, and forests. Furthermore, for ring systems, a linear-time algorithm to perform optimal diagnosis in the probabilistic model is presented.>

The problem of fault diagnosis in multiprocessor systems is considered under a probabilistic fault model. The focus is on minimizing the number of tests that must be conducted to correctly diagnose the state of every processor in the system with high probability. A diagnosis algorithm that can correctly diagnose these states with probability approaching one in a class of systems performing slightly greater than a linear number of tests is presented. A nearly matching lower bound on the number of tests required to achieve correct diagnosis in arbitrary systems is proved. Lower and upper bounds on the number of tests required for regular systems are presented. A class of regular systems which includes hypercubes is shown to be correctly diagnosable with high probability. In all cases, the number of tests required under this probabilistic model is shown to be significantly less than under a bounded-size fault set model. These results represent a very great improvement in the performance of system-level diagnosis techniques.>

The authors present and analyze a probabilistic model for the self-diagnosis capabilities of a multiprocessor system. In this model an individual processor fails with probability p and a nonfaulty processor testing a faulty processor detects a fault with probability q. This models the situation where processors can be intermittently faulty or the situation where tests are not capable of detecting all possible faults within a processor. An efficient algorithm that can achieve correct diagnosis with high probability in systems of O(n log n) connections, where n is the number of processors, is presented. It is the first algorithm to be able to diagnose a large number of intermittently faulty processors in a class of systems that includes hypercubes. It is shown that, under this model, no algorithm can achieve correct diagnosis with high probability in regular systems which conduct a number of tests dominated by n log n. Examples of systems which perform a modest number of tests are given in which the probability of correct diagnosis for the algorithm is very nearly one.>

The problem of voting is studied for both the exact and inexact cases. Optimal solutions based on explicit computation of condition probabilities are given. The most commonly used strategies, i.e. majority, median, and plurality are compared quantitatively. The results show that plurality voting is the most powerful of these techniques and is, in fact, optimal for a certain class of probability distributions. An efficient method of implementing a generalized plurality voter when nonfaulty processes can produce differing answers is also given.>

A general procedure for error detection in complex systems, called the data block capture and analysis monitoring process, is described and analyzed. It is assumed that, in addition to being exposed to potential external fault sources, a complex system will in general always contain embedded hardware and software fault mechanisms which can cause the system to perform incorrect computations and/or produce incorrect output. Thus, in operation, the system continuously moves back and forth between error and no-error states. These external fault sources or internal fault mechanisms are extremely difficult to detect. The data block capture and analysis monitoring process is concerned with detecting deviations from the normal performance of the system, known as errors, which are symptomatic of fault conditions. The process consists of repeatedly recording a fixed amount of data from a set of predetermined observation lines of the system being monitored (i.e. capturing a block of data) and then analyzing the captured block in an attempt to determine whether the system is functioning correctly.>