The Internet of Things (IoT) is a constantly expanding system connecting countless devices for seamless data collection and exchange. This has transformed decision-making with data-driven insights across different domains. However, challenges arise concerning security and computational limitations. To strengthen IoT against cyber threats and optimize resource usage, combining quantum computing (QC) with machine learning (ML) is a promising approach. ML enables computers to learn from data and detect patterns without explicit programming. By leveraging ML algorithms, vast datasets from IoT devices can be analyzed, identifying anomalies and forecasting potential security breaches. Yet, conventional ML algorithms may need help with the complexity and scale of IoT data. QC, based on quantum mechanics, offers unparalleled computational speed and scale. Quantum ML algorithms can quickly analyze IoT datasets, identifying patterns and potential threats. This study examines the ideas behind ML, QC, and their potential collaboration within IoT networks. The research focuses on the possibility of improving the security of IoT networks by integrating QC approaches with ML. It also addresses the challenges and limitations of integrating ML and QC in the context of IoT networks. These obstacles include hardware constraints, algorithm complexities, and the need for specialized knowledge.

Internet of Things (IoT) enables important data collection of the sensor nodes at desired location through device-to-device communication. It helps us in various applications including tracking of physical objects, human health monitoring, climate smart agriculture, smart manufacturing, field surveillance, and intelligent transportation. Since, these applications utilize multi-hop data transmission framework, Quality-of-Service (QoS) such as data transmission delay, data throughput, and data gathering reliability degrades at the destination nodes. In addition, multi-hop data routing causes more data interference and reduced network lifetime due to non-uniform energy consumption across the network. Moreover, in an IoT network, faulty nodes further reduce the performance of data collection and network lifetime. In order to address the aforementioned challenges, various fault detection and fault tolerant-data routing methods have been proposed in the literature. However, predicting the faulty nodes a prior can result in improved network lifetime and QoS. Hence, in this work, a novel joint node fault prediction based optimal data routing method is proposed in an IoT network. The method utilizes a novel unsupervised learning based Local Outlier Factor (LOF) method for predicting forthcoming faults. The method classifies the faulty state of a sensor node as an outlier when plotted with normal state of the sensor node. Subsequently, a novel data routing method is proposed which utilizes Q-learning framework towards multi-hop data routing. Here, the Q-values decide the optimal routing path, where, data transmission path is altered based on predictions made on the faulty nodes. The performance of the proposed methods is evaluated over both, simulated IoT testbed and real-field dataset. The obtained results demonstrate that the proposed methods are able to successfully predict the faulty nodes and avoid data transmission through them, resulting in improved energy-efficiency and QoS over the network.

Global routing has become more challenging due to advancements in the technology node and the ever-increasing size of chips. Global routing needs to generate routing guides such that (1) routability of detailed routing is considered and (2) the routing is deterministic and fast. In this paper, we firstly introduce soft capacity which reserves routing space for detailed routing based on the pin density and Rectangular Uniform wire Density (RUDY). Second, we propose a deterministic parallelization approach that partitions the netlist into batches and then bulk-synchronously maze-routes a single batch of nets. The advantage of this approach is that it guarantees determinacy without requiring the nets running in parallel to be disjoint, thus guaranteeing scalability. We then design a scheduler that mitigates the load imbalance and livelock issues in this bulk synchronous execution model. We implement SPRoute 2.0 with the proposed methodology. The experimental results show that SPRoute 2.0 generates good quality of results with 43% fewer shorts, 14% fewer DRCs and a 7.4X speedup over a state-of-the-art global router on the ICCAD2019 contest benchmarks.

Testing concurrent systems remains an uncomfortable problem for developers. The common industrial practice is to stress-test a system against large workloads, with the hope of triggering enough corner-case interleavings that reveal bugs. However, stress testing is often inefficient and its ability to get coverage of interleavings is unclear. In reaction, the research community has proposed the idea of systematic testing, where a tool takes over the scheduling of concurrent actions so that it can perform an algorithmic search over the space of interleavings.We present an experience paper on the application of systematic testing to several case studies. We separate the algorithmic advancements in prior work (on searching the large space of interleavings) from the engineering of their tools. The latter was unsatisfactory; often the tools were limited to a small domain, hard to maintain, and hard to extend to other domains. We designed Nekara, an open-source cross-platform library for easily building custom systematic testing solutions.We show that (1) Nekara can effectively encapsulate state-of-the-art exploration algorithms by evaluating on prior bench-marks, and (2) Nekara can be applied to a wide variety of scenarios, including existing open-source systems as well as production distributed services of Microsoft Azure. Nekara was easy to use, improved testing, and found multiple new bugs.

Hypergraph partitioning is used in many problem domains including VLSI design, linear algebra, Boolean satisfiability, and data mining. Most versions of this problem are NP-complete or NP-hard, so practical hypergraph partitioners generate approximate partitioning solutions for all but the smallest inputs. One way to speed up hypergraph partitioners is to exploit parallelism. However, existing parallel hypergraph partitioners are not deterministic, which is considered unacceptable in domains like VLSI design where the same partitions must be produced every time a given hypergraph is partitioned.

We present a new deterministic algorithm for distributed weighted all pairs shortest paths (APSP) in both undirected and directed graphs. Our algorithm runs in ~O(n4/3 ) rounds in the Congest models on graphs with arbitrary edge weights, and it improves on the previous ~O(n3/2) bound of Agarwal et al. [ARKP18]. The main components of our new algorithm are a new faster technique for constructing blocker set deterministically and a new pipelined method for deterministically propagating distance values from source nodes to the blocker set nodes in the network. Both of these techniques have potential applications to other distributed algorithms.

We present new results for the distributed computation of all pairs shortest paths (APSP) in the CONGEST model in an n-node graph with moderate non-negative integer weights. Our methods can handle zero-weight edges which are known to present difficulties for distributed APSP algorithms. The current best deterministic distributed algorithm in the CONGEST model that handles zero weight edges is the Õ(n3/2)-round algorithm of Agarwal et al. [3] that works for arbitrary edge weights. Our new deterministic algorithms run in O(W1/4· n5/4) rounds in graphs with non-negative integer edge-weight at most W, and in Õ(n·Δ1/3) rounds for shortest path distances at most Δ. These algorithms are built on top of a new pipelined algorithm we present for this problem that runs in at most 2n√Δ + 2n rounds. Additionally, we show that the techniques in our results simplify some of the procedures in the earlier APSP algorithms for non-negative edge weights in [3], [13]. We also present new results for computing h-hop shortest paths from k given sources, including the notion of consistent h-hop shortest path trees, and we present an O(n/ϵ2)-round deterministic (1+ϵ) approximation algorithm for graphs with non-negative poly(n) integer weights, improving results in [16], [18] that hold only for positive integer weights.

We present a deterministic distributed algorithm to compute all-pairs shortest paths (APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in Õ (n^3/2 ) rounds in the Congest model, where n is the number of nodes in the graph. This is the first o(n^2) rounds deterministic distributed algorithm for the weighted APSP problem. Our algorithm is fairly simple and incorporates a deterministic distributed algorithm we develop for computing a 'blocker set' [King99], which has been used earlier in sequential dynamic computation of APSP.

We consider the fine-grained complexity of sparse graph problems that currently have Õ(mn) time algorithms, where m is the number of edges and n is the number of vertices in the input graph. This class includes several important path problems on both directed and undirected graphs, including APSP, MWC (Minimum Weight Cycle), Radius, Eccentricities, BC (Betweenness Centrality), etc.

We present algorithms and techniques for several problems related to finding multiple simple shortest paths and cycles in a graph. Our main result is a new algorithm for finding k simple shortest paths for all pairs of vertices in a weighted directed graph G = (V, E). For k = 2 our algorithm runs in O(mn + n^2 log n) time where m and n are the number of edges and vertices in G. For k = 3 our algorithm runs in O(mn^2 + n^3 log n) time, which is almost a factor of n faster than the best previous algorithm. Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. We present new algorithms for generating simple cycles and simple paths in G in non-decreasing order of their weight. The algorithm for generating simple paths is much faster,and uses another variant of path extensions.