Dividing a network into clusters is a well-established strategy to address scalability challenges in data collection. With the advent of multi-access edge computing, unmanned aerial vehicles (UAVs) are increasingly being deployed to collect data from these clusters. For efficient and scalable UAVassisted data collection, the cluster formation, beyond being energy efficient, must also satisfy several critical properties, such as maintaining uniformity in cluster shape and size, ensuring appropriate placement of cluster heads, and forming compact, multi-hop structures. When nodes are mobile, clustering also needs to be fast enough to remain consistent despite topology dynamics. Existing approaches struggle to balance these diverse requirements effectively. We propose ReClub, a novel Concurrent-Transmission (CT)-based clustering framework that enables ultra-fast, energy-efficient, and topology-aware cluster formation for UAV-assisted data collection. Extensive evaluations demonstrate that ReClub is up to 92% faster than state-of-theart approaches, while sustaining reliable data collection under mobility. Moreover, ReClub-based data aggregation supports up to 7 × higher information refresh rates, making it highly suitable for next-generation mobile and large-scale edge-assisted IoT applications where 'age of information' is critical.

The rapid advancement of the satellite industry offers unprecedented opportunities for enabling Internet of Everything (IoE) applications over satellite networks. A key characteristic of such applications is that computation cannot begin until the entire application data has been fully received at the destination. To meet strict end-to-end delay constraints, minimizing the total application delay is essential. However, this requirement violates the optimal substructure property commonly assumed in traditional shortest path routing problems. Existing routing solutions often overlook these unique computation constraints and rely on substructure-preserving heuristics, resulting in suboptimal delay performance. Moreover, they lack reliability in producing delay-guaranteed routing solutions, which leads to low task completion ratios under stringent application deadlines. To overcome this problem, we propose FlexSatIoEa routing scheme that allows for flexible buffering data over satellite networks. FlexSatIoE formulates this routing problem as an integer linear programming (ILP) problem, to provide the optimal solution. As the network scales, considering the computational intractability of ILP, FlexSatIoE further modifies the storage time-aggregated graph to comprehensively model the satellite networks’ compute, storage and transmission resources. Based on the graph extension, FlexSatIoE designs an efficient routing algorithm, enabling flexible use of buffer resources by using a flow reassignment mechanism. We conduct extensive experiments over the setting of real-world satellite networks. The results show that FlexSatIoE reduces the average delay and increases the number of completed tasks by up to 50% and 40% respectively, as compared to the existing schemes, demonstrating the superior capability and reliability of FlexSatIoE in ensuring deterministic application delays.

Programmable Logic Controllers (PLCs) are critical components in Industrial Control Systems (ICSs). Their potential exposure to external world makes them susceptible to cyber-attacks. Existing detection methods against controller logic attacks use either specification-based or learnt models. However, specification-based models require experts’ manual efforts or access to PLC’s source code, while machine learning-based models often fall short of providing explanation for their decisions. We designSRLR— aSymbolic Regression based Logic Recoverysolution to identify the logic of a PLC based only on its inputs and outputs. The recovered logic is used to generate explainable rules for detecting controller logic attacks. SRLR enhances the latest deep symbolic regression methods using the following ICS-specific properties: (1) some important ICS control logic is best represented in frequency domain rather than time domain; (2) an ICS controller can operate in multiple modes, each using different logic, where mode switches usually do not happen frequently; (3) a robust controller usually filters out outlier inputs as ICS sensor data can be noisy; and (4) with the above factors captured, the degree of complexity of the formulas is reduced, making effective search possible. Thanks to these enhancements,SRLRconsistently outperforms all existing methods in a variety of ICS settings that we evaluate. In terms of the recovery accuracy,SRLR’s gain can be as high as 39% in some challenging environment. We also evaluateSRLRon a distribution grid containing hundreds of voltage regulators, demonstrating its stability in handling large-scale, complex systems with varied configurations.

The rapid growth of Internet-of- Things (IoT) systems demands higher throughput to process sensor data. Existing data processing platforms use simple heuristics for task placement, which perform poorly. We proposed a Permutation-based Task Placement Optimizer (PTPO) that constructs a set of valid task placement permutations to formulate a mixed-integer linear programming problem. PTPO enables efficient real-time task placement for multiple dynamic applications. Our study highlights three key design factors: joint consideration of compute and network constraints, accurate profiling of resource needs, and fine-grained splitting of tasks across nodes. We demonstrate more than 80% throughput gain compared to state-of-the-art schemes using real-world IoT Applications.

Electrical substations are becoming more prone to cyber-attacks due to increasing digitalization. Prevailing defence measures based on cyber rules are often inadequate to detect attacks that use legitimate-looking measurements. In this work, we design and implement a bad data detection solution for electrical substations called ResiGate, that effectively combines a physics-based approach and a machine-learning-based approach to provide substantial speed-up in high-throughput substation communication scenarios, while still maintaining high detection accuracy and confidence. While many existing physics-based schemes are designed for deployment in control centers (due to their high computational requirement), ResiGate is designed as a security appliance that can be deployed on low-cost industrial computers at the edge of the smart grid so that it can detect local substation-level attacks in a timely manner. A key challenge for this is to continuously run the computationally demanding physics-based analysis to monitor the measurement data frequently transmitted in a typical substation. To provide high throughput without sacrificing accuracy, ResiGate uses machine learning to effectively filter out most of the non-suspicious (normal) data and thereby reducing the overall computational load, allowing efficient performance even with a high volume of network traffic. We implement ResiGate on a low-cost industrial computer and our experiments confirm that ResiGate can detect attacks with zero error while sustaining a high throughput.

How to allocate network paths and their resources to minimize the delivery time of data transfer tasks over time-varying networks? Solving this MDDT (Minimizing Data Delivery Time) problem has important applications from data centers to delay-tolerant networking. In particular, with the rapid deployment of satellite networks in recent years, an efficient MDDT solver will serve as a key building block there.The MDDT problem can be solved in polynomial time by finding the maximum flow in a time-expanded graph. A binary-search-based solver incurs O(N•log N•Γ) time complexity, where N corresponds to time horizon and Γ is the time complexity to solve a maximum flow problem for one snapshot of the network. In this work, we design a one-pass solver that progressively expands the graph over time until it reaches the earliest time interval n to complete the delivery. By reusing the calculated maximum flow results from earlier iterations, it solves the MDDT problem while incurring only O(nΓ) time complexity for algorithms that can apply our technique. We apply the one-pass design to Ford-Fulkerson algorithm and evaluate our solver using a network of 184 satellites from Starlink constellations. We demonstrate >75× speed-up in the running time and show that our solution can also enable advanced applications such as preemptive scheduling.

We study the cost of distributed MST construction in the setting where each edge has a latency and a capacity, along with the weight. Edge latencies capture the delay on the links of the communication network, while capacity captures their throughput (the rate at which messages can be sent). Depending on how the edge latencies relate to the edge weights, we provide several tight bounds on the time and messages required to construct an MST.When edge weights exactly correspond with the latencies, we show that, perhaps interestingly, the bottleneck parameter in determining the running time of an algorithm is the total weight W of the MST (rather than the total number of nodes n, as in the standard CONGEST model). That is, we show a tight bound of $\tilde \Theta $ (D + $\sqrt {W/c} $) rounds, where D refers to the latency diameter of the graph, W refers to the total weight of the constructed MST and edges have capacity c. The proposed algorithm sends Õ (m + W) messages, where m, the total number of edges in the network graph under consideration, is a known lower bound on message complexity for MST construction. We also show that Ω(W) is a lower bound for fast MST constructions.When the edge latencies and the corresponding edge weights are unrelated, and either can take arbitrary values, we show that (unlike the sub-linear time algorithms in the standard CONGEST model, on small diameter graphs), the best time complexity that can be achieved is Θ(D + n/c). However, if we restrict all edges to have equal latency ℓ and capacity c while having possibly different weights (weights could deviate arbitrarily from ℓ), we give an algorithm that constructs an MST in Õ (D + $\sqrt {n\ell /c} $) time. In each case, we provide nearly matching upper and lower bounds.

We study graph realization problems from a distributed perspective. The problem is naturally applicable to the distributed construction of overlay networks that must satisfy certain degree or connectivity properties, and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization. In the degree sequence problem, each node v is associated with a degree d(v), and the resulting degree sequence is realizable if it is possible to construct an overlay network in which the degree of each node v is d(v). The minimum threshold-connectivity problem requires us to construct an overlay network that satisfies connectivity constraints specified between every pair of nodes.Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge.The main realization algorithms we present are the following. (1) A $\tilde O(\min \{ \sqrt m ,\Delta \} )$ time algorithm for implicit realization of a degree sequence. Here, Δ = maxvd(v) is the maximum degree and m = (1/2) v d(v) is the number of edges in the final realization. (2) A $\tilde O\left( \Delta \right)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde O\left( \Delta \right)$ additional rounds. (3) A $\tilde O\left( \Delta \right)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde O\left( 1 \right)$ algorithm for implicit realization when all nodes know each other’s IDs. These algorithms are 2-approximations w.r.t. the number of edges. Our algorithms are complemented by lower bounds showing tightness up to log n factors. Additionally, we provide algorithms for realizing trees and an $\tilde O\left( 1 \right)$ round algorithm for approximate degree sequence realization.

Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs by defining φ*to be the “critical weighted conductance” and ℓ*to be the “critical latency”. One goal of this paper is to argue that φ*characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination, up to polylogarithmic factors. Specifically, we show that in a graph with (weighted) diameter D (with latencies as weights) and maximum degree Δ, any information dissemination algorithm requires at least Ω(min(D+Δ,ℓ*/φ*)) time in the worst case. We show several variants of the lower bound (e.g., for graphs with small diameter, graphs with small max-degree, etc.) by reduction to a simple combinatorial game. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D+Δ)log3n,(ℓ*/φ*)log n) time. This is achieved by combining two cases. We show that the classical push-pull algorithm is (near) optimal when the diameter or the maximum degree is large. For the case where the diameter and the maximum degree are small, we give an alternative strategy in which we first discover the latencies and then use an algorithm for known latencies based on a weighted spanner construction. (Our algorithms are within polylogarithmic factors of being tight both for known and unknown latencies.) While it is easiest to express our bounds in terms of φ*and ℓ*, in some cases they do not provide the most convenient definition of conductance in weighted graphs. Therefore we give a second (nearly) equivalent characterization, namely the average weighted conductance φavg.

Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs by defining φ*to be the "critical conductance" and ℓ*to be the "critical latency". One goal of this paper is to argue that φ*characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination, up to polylogarithmic factors. Specifically, we show that in a graph with (weighted) diameter d (with latencies as weights) and maximum degree Δ, any information dissemination algorithm requires at least Δ(min(D+Δ, ℓ*/φ*)) time in the worst case. We show several variants of the lower bound (e.g., for graphs with small diameter, graphs with small max-degree, etc.) by reduction to a simple combinatorial game. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D+Δ)log3n, (ℓ*/φ;*)\log n) time. This is achieved by combining two cases. We show that the classical push-pull algorithm is (near) optimal when the diameter or the maximum degree is large. For the case where the diameter and the maximum degree are small, we give an alternative strategy in which we first discover the latencies and then use an algorithm for known latencies based on a weighted spanner construction. (Our algorithms are within polylogarithmic factors of being tight both for known and unknown latencies.) While it is easiest to express our bounds in terms of φ*and ℓ*, in some cases they do not provide the most convenient definition of conductance in weighted graphs. Therefore, we give a second (nearly) equivalent characterization, namely the average conductance φavg.

In this paper, we look at the problem of randomized leader election in synchronous distributed networks with a special focus on the message complexity. We provide an algorithm that solves the implicit version of leader election (where non-leader nodes need not be aware of the identity of the leader) in any general network with O( √ n log7/2 n tmix ) messages and in O(tmix log2 n) time, where n is the number of nodes and tmix refers to the mixing time of a random walk in the network graph G. For several classes of wellconnected networks (that have a large conductance or alternatively small mixing times e.g. expanders, hypercubes, etc), the above result implies extremely efficient (sublinear running time and messages) leader election algorithms. Correspondingly, we show that any substantial improvement is not possible over our algorithm, by presenting an almost matching lower bound for randomized leader election. We show that Ω( √ n/Φ3/4) messages are needed for any leader election algorithm that succeeds with probability at least 1 - o(1), where Φ refers to the conductance of a graph. To the best of our knowledge, this is the first work that shows a dependence between the time and message complexity to solve leader election and the connectivity of the graph G, which is often characterized by the graph's conductance Φ. Apart from the Ω(m) bound in [23] (where m denotes the number of edges of the graph), this work also provides one of the first non-trivial lower bounds for leader election in general networks.

Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs, defining φ* to be the "weighted conductance" and l* to be the "critical latency." One goal of this paper is to argue that φ* characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination. Specifically, we show that in a graph with (weighted) diameter D (with latencies as weights), maximum degree Δ, weighted conductance φ* and critical latency l*, any information dissemination algorithm requires at least Ω(min(D+Δ, l*/φ*)) time. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D + Δ)log3n), (l*/φ*)log(n)) time.