We consider linear search for an escaping target whose speed and/or initial distance from the origin may be unknown to the searcher. The searcher (an autonomous mobile agent) is initially placed at the origin of the real line and can move with maximum speed 1 in either direction along the line. The oblivious mobile target that is moving away from the origin with a constant speed v < 1 is initially placed by an adversary on the infinite line at distance d from the origin in an unknown direction. We consider four cases, depending on whether v and/or d is known to the searcher. The main contributions of this paper are new lower bounds as well as algorithms leading to new upper bounds for search in these settings. We present tight bounds for the cases when v is known. For the cases where v is unknown, we prove an optimal (up to lower order terms in the exponent) competitive ratio in the case where d is known and improved upper and lower bounds for the case where d is unknown. These results solve an open problem proposed in Coleman et al. (2022) [11] .

Two autonomous mobile robots and a non-autonomous one, also called bike, are placed at the origin of an infinite line. The autonomous robots can travel with maximum speed 1. When a robot rides the bike its speed increases to v > 1 . Exactly one robot at a time can ride the bike, moreover the bike is non-autonomous in that it cannot move on its own. An Exit is placed on the line at a location which is unknown to the robots and at distance d from the origin. The robots have limited communication behavior; one robot is a sender (denoted by S) in that it can send information wirelessly at any distance and receive messages only in F2F (Face-to-Face), while the other robot is a receiver (denoted by R) in that it can receive information wirelessly but can send information only F2F. The bike has no communication capabilities of its own. We refer to the resulting communication model of the ensemble of the two autonomous robots and the bike as S/R. Our general goal is to understand the impact of the non-autonomous robot in assisting the evacuation of two communication-limited autonomous robots. Our main contribution is to provide a new evacuation algorithm that enables both robots to evacuate from the unknown Exit in the S/R model. We also analyze the resulting evacuation time as a function of the bike's speed v and give upper and lower bounds on the competitive ratio of the resulting algorithm for the entire range of possible values of v .

Truck platooning is an innovative logistics approach to lower operational costs, particularly fuel consumption, while addressing contemporary transportation challenges. While recent studies on truck platooning have emphasized platoons’ energy savings, stability, and safety, there has been limited exploration of platoon formation and control. This paper uses optimal control theory to address the dispatching control of trucks with arriving platoons. In particular, trucks arrive at a highway station while platoons arrive alongside it. The station controls the truck holding and dispatching, where trucks are sent out with or without a platoon. Dispatching trucks with an arriving platoon reduces fuel consumption while waiting for a platoon to arrive increases the dwell time (i.e., transportation delay). We assume that an arriving platoon determines the number of trucks (i.e., the batch size) it can accept. Only a single truck can be dispatched if a platoon is absent. Hence, we formulate the dispatching control problem and derive the optimal policy for the discounted costs and the average cost governing the dispatch of trucks alongside platoons. We proved the optimality of threshold policies. Numerical results for the average cost case are presented. They are consistent with the optimal ones.

Task migration to remote servers offers a promising solution to the congestion issue in mobile edge computing systems. Our optimal task offloading design minimizes a system cost function, encompassing offloading and penalty costs. The offloading cost reflects external server resource usage, while the penalty cost accounts for task expiration risk. To optimize the expected cost over a time horizon, we employ Dynamic Programming (DP) and analyze its properties for an optimal offloading policy. “Curse of Dimensionality” of the DP equation poses computational challenges, especially with infinite state space. To mitigate this, we identify crucial policy properties, enabling DP evaluation on a finite state subset. Moreover, we show that the computation of the optimal task offloading decision at a given state can be deduced by leveraging the optimal decision taken at its “adjacent” states. We then provide numerical results to demonstrate parameter impact and validate theoretical findings.

Task offloading in mobile edge computing systems is subject to various random factors including the connection to external servers, new task requests from users, and the availability of local processing services. However, statistical information is often not available in practical scenarios. To tackle the issue, we adopt a Q-learning-based approach that learns the optimal task offloading policy through observations of random events. Traditional Q-learning methods may face challenges such as long training times and high memory usage due to the large state and action space. To overcome this problem, we propose a novel method that leverages the concept of adjacent state sequence. In this type of sequence, we can infer the optimal offloading decision of a system state from other states. This method aims to improve the convergence speed and memory efficiency of the learning model by reducing the number of parameters that need to be learned and stored. Those eliminated parameters instead can be computed via a derived linear expression. We conduct experiments to demonstrate the enhancement of our proposed method compared to the traditional$\mathbf{Q}-$learning in the studied problem.

Truck platooning is a promising technology that can reduce costs (fuel consumption) and enhance the overall transportation productivity. While recent research has focused on platoons' network and stability, few studies have tackled platooning formation and control. This paper uses Reinforcement Learning (RL) to study the dispatching control of trucks with arriving platoons, a problem first proposed in [1]. This work builds on [1] by considering the lack of the cost function and statistical knowledge. In particular, we employ Q-learning to compute the optimal dispatch control policy at a highway hub. Given the unbounded state space of the model, traditional Q-learning may converge slowly or even get stuck in sub-optimal policies. We improve Q-learning by confining the agent to transition in a finite subset of the state space. For this purpose, we use the switching condition property of the optimal policy (derived in [1]), the underlying random walk model, and a sensitivity analysis of the cost function. Our numerical results demonstrate that our Enhanced Q-learning converges significantly faster (up to 97%) in terms of CPU time and number of interactions.

As the automotive industry is developing autonomous driving systems and vehicular networks, attention to truck platooning has increased as a way to reduce costs (fuel consumption) and improve efficiency in the highway. Recent research in this area has focused mainly on the aerodynamics, network stability, and longitudinal control of platoons. However, the system aspects (e.g., platoon coordination) are still not well explored. In this paper, we formulate a platooning coordination problem and study whether trucks waiting at an initial location (station) should wait for a platoon to arrive in order to leave. Arrivals of trucks at the station and platoons by the station are modelled by independent Bernoulli distributions. Next we use the theory of Markov Decision Processes to formulate the dispatching control problem and derive the optimal policy governing the dispatching of trucks with platoons. We show that the policy that minimizes an average cost function at the station is of threshold type. Numerical results for the average cost case are presented. They are consistent with the optimal ones.

Quantum data communications and networking involve classical hardware and software. Quantum storage is sensitive to environmental disturbances that may have malicious origins. Teleportation and entanglement swapping, two building blocks for the future quantum Internet, rely on secure classical bit communications. When lack of authenticity, integrity, and replay protection may have a high impact, quantum data communications are at risk and need to be protected. Building upon quantum cryptography and random generation of quantum operators, we propose a solution to protect the authenticity, integrity, and replay of quantum data communications. Our solution includes a classical data interface to quantum data cryptography. We describe how classical keying material can be mapped to quantum operators. This enables classical key management techniques for secure quantum data communications.

We consider evacuation of a group of $n \geq 2$ autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed $1$ in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio ($CR$) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio $CR=3+2 \sqrt{2}$. If there is a single sender or fully wireless agent, and multiple receivers we prove that $CR \in [2+\sqrt{5},5]$, and if there are multiple senders and a single receiver or fully wireless agent, we show that $CR \in [3,5.681319]$. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of $d$, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least $9d-o(d)$. It was shown recently that $k\geq2$ robots traveling at unit speed also require at least $9d$ group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance $x$ at constant speed $s$ is given by $s^2 x$. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple $c$ of the distance $d$ and the speed of the robots is bounded by $b$. Motivation for this study is that for the case when robots must complete the search in $9d$ time with maximum speed one, a single robot requires at least $9d$ energy, while for two robots, all previously proposed algorithms consume at least $28d/3$ energy. When the robots have bounded memory, we generalize existing algorithms to obtain a family of optimal (and in some cases nearly optimal) algorithms parametrized by pairs of $b,c$ values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. We also propose a novel search algorithm, with unbounded memory, that simultaneously achieves search time $9d$ and consumes energy $8.42588d$. Our result shows that two robots can search on the line in optimal time $9d$ while consuming less total energy than a single robot within the same search time.

Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds.

We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and "measuring instruments'' of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.

Two anonymous robots placed at different positions on an infinite line need to rendezvous. Each robot possesses a clock which it uses to time its movement. However, the robot's individual parameters in the form of their walking speed and time unit may or may not be the same for both robots. We study the feasibility of rendezvous in different scenarios, in which some subsets of these parameters are not the same. As the robots are anonymous, they execute the same algorithm and when both parameters are identical the rendezvous is infeasible. We propose a universal algorithm, such that the robots are assured of meeting in finite time, in any case when at least one of the parameters is not equal for both robots.

We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A team of two robots start from the center of the disk, and their goal is to fetch the treasure to the exit. At any time the robots can move anywhere they choose on the disk, independently of each other, with the same speed. A robot detects an interesting point (treasure or exit) only if it passes over the exact location of that point. We are interested in designing distributed algorithms that minimize the worst-case treasure-evacuation time, i.e. the time it takes for the treasure to be discovered and brought (fetched) to the exit by any of the robots. The communication protocol between the robots is either wireless, where information is shared at any time, or face-to-face (i.e. non-wireless), where information can be shared only if the robots meet. For both models we obtain upper bounds for fetching the treasure to the exit. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can exchange information without meeting, effectively achieving a highly efficient treasure-evacuation protocol which is minimally affected by the lack of distant communication. Finally, we complement our positive results above by providing a lower bound in the face-to-face model.

Abstract. A fence, represented by a unit interval is to be patrolled collectively by n robots. At any moment a robot may move in one of the two possible states: walking or patrolling. Each state is associated with a maximal moving speed which cannot be exceeded. A robot may have a unique pair of speeds, but its patrolling speed is always smaller than its walking speed. Each robot is allowed to patrol while moving only in one of the two directions (not necessarily the same for all robots). We want to schedule the perpetual movements of the robots so as to minimize the idleness, defined as the smallest time interval within which every point is always visited by some robot. First, we give a centralized algorithm constructing schedules with optimal idleness, and subsequently we show a nice application to a transportation problem concerning Scheduling with Regular Delivery. Our main contribution is the study of distributed, dynamical schedules for patrolling robots with only primitive capabilities. Surprisingly we are able to design a dynamic schedule for very weak collections of two robots (silent, oblivious, passively mobile), achieving the optimal idleness. Our algorithm defines a dynamical system of memoryless robots moving back and forth in an interval. In general, analysis of the system dynamics is very complex. Part of our contribution is a very technical analysis of the dynamics of special families of dynamical systems of n robots that we call regular. For such systems we also propose a highly non-trivial O(n2) algorithm to decide whether or not robots converge to a stable configuration thus verifying if the dynamic schedule is optimal. It turns out that a very natural family of

We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of S_d (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

We consider the problem of searching on a line using n mobile robots, of which at most f are faulty, and the remaining are reliable. The robots start at the same location and move in parallel along the line with the same speed. There is a target placed on the line at a location unknown to the robots. Reliable robots can find the target when they reach its location, but faulty robots cannot detect the target. Our goal is to design a parallel algorithm minimizing the competitive ratio, represented by the worst case ratio between the time of arrival of the first reliable robot at the target, and the distance from the source to the target.

Under use of the regulated radio spectrum is being addressed using a cognitive radio network approach termed dynamic spectrum access. Primary users have priority over the regulated radio spectrum. Secondary users may use the residual air time. We focus on the problem of meeting on a common channel by a group of secondary users. Under the asymmetric model, the secondary users have different sets of available channels. If the sets are not disjoint, they can eventually make rendezvous. The goal is to make the secondary users rendezvous on a common channel in a minimum amount of time. The jump-stay rendezvous algorithm has been created by Lin et al. to solve this problem. We develop a new analysis for the two-user expected time to rendezvous in the jump-stay rendezvous algorithm, under the asymmetric model, that better reflects its performance.

We study the problem of establishing rendezvous between two secondary users. We assume that each user has two radios that can be used concurrently. We present the bidirectional algorithm that exploits the two radios. Assuming the availability of m channels, rendezvous between two start-asynchronous users is guaranteed within a delay of m time slots. The expected time-to-rendezvous is m/3 time slots. Assuming users are start-synchronous, rendezvous is made in at most (m+1)/2 time slots. The expected time-to-rendezvous is m/4 + 1 - 1/4m time slots.

We consider a problem of supplying electricity to a set of N customers in a smart-grid framework. Each customer requires a certain amount of electrical energy which has to be supplied during the time interval [0, 1]. We assume that each demand has to be supplied without interruption, with possible duration between ℓ and r, which are given system parameters (ℓ ≤ r). At each moment of time, the power of the grid is the sum of all the consumption rates for the demands being supplied at that moment. Our goal is to find an assignment that minimizes the power peak - maximal power over [0, 1] - while satisfying all the demands. To do this first we find the lower bound of optimal power peak. We show that the problem depends on whether or not the pair ℓ, r belongs to a “good” region G. If it does - then an optimal assignment almost perfectly “fills” the rectangle time × power = [0, 1] × [0, A] with A being the sum of all the energy demands - thus achieving an optimal power peak A. Conversely, if ℓ, r do not belong to G, we identify the lower bound A̅ > A on the optimal value of power peak and introduce a simple linear time algorithm that_almost_perfectly arranges all the demands in a rectangle [0, A/A̅] × [0, A̅] and show that it is asymptotically optimal.

We consider a problem of scheduling electric power demands in a smart-grid framework. Our model consists of n energy requirements {Ai, ℓi, ri}ni=1, needed to be scheduled in time interval [0,1]. Here Ai is the amount of energy, while ℓiand n are respectively, the left and right constraints on the length of the time period, during which Aihas to be supplied without interruption. The triples are assumed to be i.i.d. random vectors, with A distributed according to some general distribution G, and pair (ℓ, r) distributed uniformly in the region {0 ≤ ℓi≤ r ≤ 1}. Our goal is to find a scheduling policy minimizing the power peak - maximal power over [0,1] - and/or the operational convex cost of the system while satisfying all the demands. The problem becomes very complicated as the number n of demands increases. To address this issue, we consider an asymptotic approach, in which the average amount of energy in each demand is inversely proportional to n, thus keeping the total scheduled amount stable. In this paper we first introduce lower bounds for both types of costs and then introduce a scheduling algorithm, asymptotically optimal in the sense that its cost converges to a corresponding lower bound almost surely, as n increases to infinity. Moreover, the algorithm is on-line (each demand is scheduled at the time its parameters become known) and has fully linear running time.

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study the problem in the distributed setting. We assume each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within Θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take Θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires Ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle.

A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their uniform maximum speeds. The quality of patrolling is measured by the idleness, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idleness.

Assume that n sensors with identical range r = f(n)⁄2n, for some f(n) ≥ 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0, 1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) -- 1 the expected total displacement is shown to be Θ(√n). For senors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O(√ ln n/f(n)) while the second holds for 12 ≤ f(n) ≤ ln n -- 2 ln ln n and gives an upper bound of O(lnn⁄ f(n)ef(n)/2). Note that the second algorithm improves upon the first for f(n) > ln ln n -- ln ln ln n. Further we show a lower bound, for any 1 < f(n) < √n of Ω(εf(n)ε--(1+ε)f(n)), ε > 0.

We consider a 3D antenna orientation problem for maintaining connectivity of a wireless network in 3D space using only directional antennae. Sensors are located at points in 3D space and are equipped with directional antennae. The strong connectivity antenna orientation problem is concerned with deciding whether or not for given solid angle Ω and range r it is possible to orient the antennae so as to ensure that the sensor network resulting from the induced transmissions is strongly connected. In this paper we 1) present an algorithm ensuring optimal antenna range for the case when Ω ≥ 18π/5, 2) show that determining whether or not there exists a strong orientation of directional sensors of solid angle Ω; 0, and 3) provide an algorithm for approximating the antennae range so as to ensure strong connectivity of the resulting graph, provided the solid angle of the antennae is 2π ≤ Ω <; 18π/5· In addition, we study the effect of replacing omnidirectional antennae with directional antennae on the hop stretch factor of the resulting network of directional antennae and present some simulation results on the variation of hop stretch factor with different network sizes and solid angles of directional antennae. This is the first paper concerning the strong connectivity antennae orientation problem in 3D space.

This paper discusses the multi-robot, multi-depot Map Visitation Problem, a multi-robot inspection problem in which a team of robots originating from multiple home base depots must visit a collection of previously identified critical locations in a two-dimensional navigation environment. In its precise focus on location inspection, it is related yet complementary to other inspection or surveillance problems such as boundary coverage or patrol. In the paper, we analyze graph representations and an agent model appropriate for the Map Visitation Problem, and we present complexity results for a variety of categories of map structures, including lines, rings, trees, and general graphs. In addition to complexity results, we present an algorithm for the Map Visitation Problem on trees that is optimal for single-robot problems and a second algorithm that is provably within a factor of two of optimal for two robots inspecting arbitrary graphs.

We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2 t state agent which can achieve rendezvous on an n -node ring in expected time O ( n 2 /2 t + 2 t ) and that any t /2 state agent requires expected time Ω( n 2 /2 t ). As a corollary we observe that Θ(log log n ) bits of memory are necessary and sufficient to achieve rendezvous in linear time.

The core of the Optimized Link State Routing (OLSR) protocol is the selection of Multipoint Relays (MPRs) as a flooding mechanism for distributing control traffic messages. A node in an OLSR network, selects its MPR set such that all two-hop neighbors are reachable through, at least, one MPR. However, if an MPR misbehaves during the execution of the protocol, the connectivity of the network is compromised. Additional coverage in the selection of the MPRs helps to mitigate the effect of control traffic attacks. RFC3626 defines the selection of MPRs with additional coverage. Nevertheless, the overhead of the network increases due to the added number of control traffic messages. In this paper, we propose an improved MPR selection with additional coverage. Every node selects, if it is possible, k + 1 disjoint MPR sets. The union of those sets, is a k-robust-MPR set. Thus, given a node, alternative paths are created to reach any destination two-hops away. We test both approaches against two kinds of adversaries misbehaving during the execution of the protocol. Our proposed MPR selection with additional coverage mitigates the effect of control traffic attacks by offering equivalent protection compared to the MPR selection with extra coverage presented in RFC3626, but reducing the overhead generated by redundant control information.

In WiMAX/IEEE 802.16 with mobility support, scanning for an available channel by a mobile station, especially during a handover, must be done promptly in order to reduce delays in network access. We have shown previously that mobile stations can reduce scanning times by maintaining a most probable list of frequencies in use. In this paper, we extend this idea to further capture the mobility patterns of users. By using time-of-day and location-based mobility profiles a mobile station improves scanning performance during handovers. We show this improvement by modeling and simulating an area of WiMAX coverage with various mobility patterns and real-world mobility traces.

We describe a novel Distributed Storage protocol in Disruption (Delay) Tolerant Networks (DTN). Since DTNs can not guarantee the connectivity of the network all the time, distributed data storage and look up has to be performed in a store-and-forward way. In this work, we define local distributed location regions which are called cells to facilitate the data storage and look up process. Nodes in a cell have high probability of moving within their cells. Our protocol resorts to storing data items in cells which have hierarchical structure to reduce routing information storage at nodes. Multiple copies of a data item may be stored at nodes to counter the adverse impact of the nature of DTNs. The cells are relatively stable regions and as a result, data exchange overheads among nodes are reduced. Through experimentation, we show that the proposed distributed storage protocol achieves higher successful data storage ratios with lower delays and limited data item exchange requirements than other protocols in the literature.

We study the connectivity and diameter of the fault-free part of n-node networks where nodes fail in a random dependent way. To capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, causing faults in the given node and its neighbors; faults at distance at most 2 become dependent. We investigate the impact of the spot probability on the connectivity and diameter of the fault-free part of the network. We show a network which has a low diameter with high probability, if p ≤ 1/c log n. We also show that, for constant spot probabilities, most classes of networks do not have their fault-free part connected with high probability. For smaller spot probabilities, connectivity with high probability is supported even by bounded degree networks: the torus supports connectivity with high probability when p ε 1/ω(n1/2), and does not when p ε 1/O(n1/2); a network built of tori is designed, with the same fault-tolerance properties and additionally having low diameter. We show, however, that for networks of degree bounded above by a constant Δ, the fault-free part can not be connected with high probability if p ε 1/O(n1/Δ). This is the first analytic paper which investigates the connectivity and diameter of networks where nodes fail in a random dependent way. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

It is a classical result of Stein and Waterman that the asymptotic number S(n) of RNA secondary structures is 1.104366 ldr n-3/2ldr 2.618034n, where the combinatorial model of RNA concerns a length n homopolymer, such that any base can pair with any other base, subject to the usual convention that hairpin loops must contain at least thetas = 1 unpaired bases. The result of Stein and Waterman is proved by developing recursions,using generating functions and applying Bender's theorem. These recursions form the basis to compute the minimum free energy secondary structure for a given RNA sequence, with respect to the Nussinov energy model, later extended by Zuker to substantially more complicated resursions for the Turner nearest neighbor energy model. In this paper, we study combinatorial asymptotic for two special subclasses of RNA secondary structures - canonical and saturated structures. Canonical secondary structures are defined to have no lonely (isolated) base pairs. This class of secondary structures was introduced b y Bompfuenewerer et al., who noted that the runtime of Vienna RNA Package is substantially decreased when restricting computations to canonical structures. Here we provide an explanation for the speed-up, by proving that the asymptotic number of canonical RNA secondary structures is 2.1614 ldr n-3/2ldr 1.96798n. Saturated secondary structures have the property that no base pairs can be added without violating the definition of secondary structure (i.e. introducing a pseudoknotor base triple). In the Nussinov energy model,where the energy for a base pair is -1, saturated structures correspond to kinetic traps.n prior work, we showed that the asymptotic number of saturated structures of a length n homopolymer is 1.07427 ldr n-3/2ldr 2.35467n. In this paper, we show that the expected number of base pairs of random saturated structures, generated by a natural stochastic procedure, is (zthetas+1)/((1-z)2) (-z-Sigmai=0thetas(z2)/(i+1)) (int e (z+Sigmai=0thetas(z2)/(i+1))dz).

The propagation speed of fast scanning worms and the stealthy nature of slow scanning worms present unique challenges to intrusion detection. Typically, techniques optimized for detection of fast scanning worms fail to detect slow scanning worms, and vice versa. In practice, there is interest in developing an integrated approach to detecting both classes of worms. In this paper, we propose and analyze a unique integrated detection approach capable of detecting and identifying traffic flow(s) responsible for simultaneous fast and slow scanning malicious worm attacks. The approach uses a combination of evidence from distributed host-based anomaly detectors, a self-adapting profiler and Bayesian inference from network heuristics to detect intrusion activity due to both fast and slow scanning worms. We assume that the extreme nature of fast scanning worm epidemics make them well suited for extreme value theory and use sample mean excess function to determine appropriate thresholds for detection of such worms. Random scanning worm behavior is considered in analyzing the stochastic time intervals that affect behavior of the detection technique. Based on the analysis, a probability model for worm detection interval using the detection scheme was developed. Simulations are used to validate our assumptions and analysis.

Detection of slow worms is particularly challenging due to the stealthy nature of their propagation techniques and their ability to blend with normal traffic patterns. In this paper, we propose a distributed detection approach based on the generalized evidence processing (GEP) theory, a sensor integration and data fusion technique. With GEP theory, evidence collected by distributed detectors determine the probability associated with a detection decision under a hypothesis. The collected evidence is combined to arrive at an optimal fused detection decision by minimizing a cumulative decision risk function. Typically, malicious traffic flows of varying scanning rates can occur in the wild, and the difficulty in detecting slow scanning worms in particular can be exacerbated by interference from other traffic flows scanning at faster rates. Our proposed detection technique uses a window-based self adapting profiler to filter detected malicious traffic profiles with scanning rates greater than the low scanning rates we are interested in. Experiments on a live test-bed are used to demonstrate behavior of the technique.

We investigate the problem of converting sets of sensors into strongly connected networks of sensors using multiple directional antennae. Consider a set S of n points in the plane modeling sensors of an ad hoc network. Each sensor uses a fixed number, say 1 ≤ k ≤ 5, of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius). We give algorithms for orienting the antennae at each sensor so that the resulting directed graph induced by the directed antennae on the nodes is strongly connected. We also study trade-offs between the total angle spread and range for maintaining connectivity.

We describe a Fast Delivery Guaranteed Face Routing (FDGF) in ad hoc wireless networks. Since it is expensive for wireless nodes to get the whole network topology information, geometric routing decisions should be made locally by nodes using location information of neighboring nodes which are at most k hops away. In this paper, we first define k-local algorithm and obtain two local geometric graphs, i.e., k-Local Delauany Triangulation Graph (k-LDTG) and k-Local Minimum Weight Spanning Tree (k-LMWST), which are more efficient than existing definitions. We present problems with existing face routing protocols and propose FDGF to counter possible long delivery delay with high probability. The performance of face routing differs on different planar graphs. We compare face routing characteristics of four different underlying routing graphs which include k-LDTG, Gabriel Graph (GG), Relative Neighbor Graph (RNG) and k-LMWST. Due to different attributes of these graphs, the message delivery delay, routing hop and minimum energy consumption differ greatly. Through experimentation in the NS-2 simulator, we have shown that the proposed face routing protocol achieves 100% delivery ratio on Unit Disk Graph (UDG) when source to destination connection path exists. Face routing on k-LDTG is fast with less relay hops and face routing on k-LMWST is energy efficient. RNG achieves desirable minimum energy consumption attribute, better than all the others when the propagation model is free space and close to k-LMWST when the propagation model is Two Ray Ground.

We study the problem of maintaining connectivity in a wireless network where the network nodes are equipped with directional antennas. Nodes correspond to points on the plane and each uses a directional antenna modeled by a sector with a given angle and radius. The connectivity problem is to decide whether or not it is possible to orient the antennas so that the directed graph induced by the node transmissions is strongly connected. We present algorithms for simple polynomial-time-solvable cases of the problem, show that the problem is NP-complete in the $2$-dimensional case when the sector angle is small, and present algorithms that approximate the minimum radius to achieve connectivity for sectors with a given angle. We also discuss several extensions to related problems. To the best of our knowledge, the problem has not been studied before in the literature.

We exploit for defensive purposes the concept of darkports ­ the unused ports on active systems. We are particularly in- terested in such ports which transition to become active (i.e. become trans-darkports). Darkports are identified by pas- sively observing and characterizing the connectivity behav- ior of internal hosts in a network as they respond to both le- gitimate connection attempts and scanning attempts. Dark- ports can be used to detect sophisticated scanning activity, enable fine-grained automated defense against automated malware attacks, and detect real-time changes in a network that may indicate a successful compromise. We show, in a direct comparison with Snort, that darkports offer a better scanning detection capability with fewer false positives and negatives. Our results also show that the network awareness gained by the use of darkports enables active response op- tions to be safely focused exclusively on those systems that directly threaten the network.

It is well known that the Border Gateway Protocol (BGP), the IETF standard interdomain routing protocol, is vulnerable to a variety of attacks, and that a single misconfigured or malicious BGP speaker could result in large-scale service disruption. In this paper, we present Pretty Secure BGP (psBGP) ---a proposal for securing BGP, including an architectural overview, design details for significant aspects, and preliminary security and operational analysis. psBGP differs from other security proposals (e.g., S-BGP and soBGP) in that it makes use of a single-level PKI for AS number authentication, a decentralized trust model for verifying the propriety of IP prefix origin, and a rating-based stepwise approach for AS_PATH (integrity) verification. psBGP trades off the strong security guarantees of S-BGP for presumed-simpler operation, e.g., using a PKI with a simple structure, with a small number of certificate types, and of manageable size. psBGP is designed to successfully defend against various (nonmalicious and malicious) threats from uncoordinated BGP speakers, and to be incrementally deployed with incremental benefits.

Malicious mass-mailing activity on the Internet is a serious and continuing threat that includes mass-mailing worms, spam, and phishing. A mechanism commonly used to deliver such malicious mass mail is an SMTP-engine, which turns an infected system into a malicious mail server. We present a technique that enables, within a single mailing attempt in many popular network environments, detection and containment of (even zero-day) SMTP-engine based mass-mailing activity. Contrary to other mass-mailing detection techniques our approach is content independent and requires no attachment processing, network traffic correlation, statistical measures, or system behavioral analysis. It relies instead on the observation of DNS MX queries within the enterprise network. This stateless detection technique requires minimal computational resources making it ideally suited for real-time wire-speed deployment.

Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in P. Bose et al. (2002) that we propose has the best performance

Remote attestation in trusted computing is about the ability of a local platform to authenticate the hardware and the software stack running on a remote trusted platform. We say that this process is successful, if a local platform is able to authenticate each layer in the remote stack; it is meaningful if, by using this information, the local platform can make its own evaluation on the safety of the platform environment where the remote application is running. In this paper we analyze the credentials and beliefs that are necessary to a local platform in order for the remote attestation process to be both successful and meaningful.

Abstract We address the problem of discovering routes in strongly connected planar geometric networks with directed links. Motivated by the necessity for establishing communication in wireless ad hoc networks in which the only information available to a vertex is its immediate neighborhood, we are considering routing algorithms that use the neighborhood information of a vertex for routing with constant memory only. We solve the problem for three types of directed planar geometric networks: Eulerian (in which every vertex has the same number of incoming and outgoing edges), Outerplanar in which a single face contains all vertices of the network, and Strongly Face Connected, a new class of geometric networks that we define in the article, consisting of several faces, each face being a strongly connected outerplanar graph. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 7–15 2006

Signature-based schemes for detecting Internet worms often fail on zero-day worms, and their ability to rapidly react to new threats is typically limited by the requirement of some form of human involvement to formulate updated attack signatures. We propose an anomaly-based detection technique detailing a method to detect propagation of scanning worms within individual network cells, thus protecting internal networks from infection by internal clients. Our software implementation indicates that this technique is both accurate and rapid enough to enable automatic containment and suppression of worm propagation within a network cell. Our approach relies on an aggregate anomaly score, derived from the correlation of address resolution protocol (ARP) activity from individual network attached devices. Our preliminary analysis and prototype indicate that this technique can be used to rapidly detect zero-day worms within a very small number of scans

For the purpose of anomaly-based intrusion detection in mobile networks, the utilization of profiles, based on hardware signatures, calling patterns, service usage, and mobility patterns, have been explored by various research teams and commercial systems, namely the fraud management system by Hewlett-Packard and Compaq. This paper examines the feasibility of using profiles, which are based on the mobility patterns of mobile users, who make use of public transportation, e.g. bus. More specifically, a novel framework, which makes use of an instance based learning technique, for classification purposes, is presented. In addition, an empirical analysis is conducted in order to assess the impact of two key parameters, the sequence length and precision level, on the false alarm and detection rates. Moreover, a strategy for enhancing the characterization of users is also proposed. Based on simulation results, it is feasible to use mobility profiles for anomaly-based intrusion detection in mobile wireless networks.

Summary form only given. The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications. The first such algorithms were able to traverse triangulated subdivisions. Later these algorithms were extended to traverse vertices of an arrangement or a convex polytope. The research progress culminated in an algorithm that can traverse any planar subdivision. We extend the notion of planar subdivision to quasiplanar subdivision in which we allow many edges to cross each other. We describe an algorithm to traverse any quasiplanar subdivision that satisfies a simple requirement. The worst case running time of our algorithm is O(|E| log |E|), which matches the running time of the traversal algorithm for planar subdivisions.

In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the network is anonymous, however, the resulting symmetry can make the problem impossible to solve. Symmetry is typically broken by having the mobile agents run either a randomized algorithm or different deterministic algorithms. We investigate the use of identical tokens to break symmetry so that the two mobile agents can run the same deterministic algorithm. After deriving the explicit conditions under which identical tokens can be used to break symmetry on the n node ring, we derive the lower and upper bounds for the time and memory complexity of the rendezvous search problem with various parameter sets. While these results suggest a possible tradeoff between the mobile agents' memory and the time complexity of the rendezvous search problem, we prove that this tradeoff is limited.

Abstract We consider the problem of searching for a piece of information in a fully interconnected computer network (also called a complete network orclique) by exploiting advice about its location from the network nodes. Each node contains a database that “knows” what kind of documents or information are stored in other nodes (e.g., a node could be a Web server that answers queries about documents stored on the Web). The databases in each node, when queried, provide a pointer that leads to the node that contains the information. However, this information is up‐to‐date (or correct) with some bounded probability. While, in principle, one may always locate the information by simply visiting the network nodes in some prescribed ordering, this requires a time complexity in the order of the number of nodes of the network. In this paper, we provide algorithms for locating an information node in the complete communication network, which take advantage ofadvicegiven from network nodes. The nodes may either give correct advice, by pointing directly to the information node, or give wrong advice, by pointing elsewhere. On the lower‐bounds' side, we show that no fixed‐memory (i.e., with memory independent of the network size) deterministic algorithm may locate the information node in a constant (independent of the network size) expected number of steps. Moreover, ifp= ω(1/n) is the probability that a node of ann‐node clique gives correct advice, we show that no algorithm may locate the information node in an expected number of steps less than 1/p−o(1). To study how the expected number of steps is affected by the amount of memory allowed to the algorithms, we give a memoryless randomized algorithm with expected number of steps 4/p+o(1/p) +o(1) and a 1‐bit randomized algorithm requiring on the average at most 2/p+o(1) steps. In addition, in the memoryless case, we also prove a 4/plower bound for the expected number of steps in the case where the nodes giving faulty advice may decide on the content of this advice in any possible way and not merely at random (adversarialfault model). Finally, for the case where faulty nodes behave randomly, we give an optimal, unlimited memory deterministic algorithm with expected number of steps bounded from above by 1/p+o(1/p) + 1. © 2003 Wiley Periodicals, Inc.

In this paper we examine the problem of searching for some information item in the nodes of a fully interconnected computer network, where each node contains information relevant to some topic as well as links to other network nodes that also contain information, not necessarily related to locally kept information. These links are used to facilitate the Internet users and mobile software agents that try to locate specific pieces of information. However, the links do not necessarily point to nodes containing information of interest to the user or relevant to the aims of the mobile agent. Thus an element of uncertainty is introduced. For example, when an Internet user or some search agent lands on a particular network node, they see a set of links that point to information that is, supposedly, relevant to the current search. Therefore, we can assume that a link points to relevant information with some unknown probability $p$ that, in general, is related to the number of nodes in the network (intuitively, as the network grows, this probability tends to zero since adding more nodes to the network renders some extant links less accurate or obsolete). Consequently, since there is uncertainty as to whether the links contained in a node's Web page are correct or not, a search algorithm cannot rely on following the links systematically since it may end up spending too much time visiting nodes that contain irrelevant information. In this work, we will describe and analyze a search algorithm that is only allowed to transfer a fixed amount of memory along communication links as it visits the network nodes. The algorithm is, however, allowed to use one bit of memory at each node as an ‘already visited’ flag. In this way the algorithm has its memory distributed to the network nodes, avoiding overloading the network links as it moves from node to node searching for the information. We work on fully interconnected networks for simplicity reasons and, moreover, because according to some recent experimental evidence, such networks can be considered to be a good approximation of the current structure of the World Wide Web.

An anonymous ring network is a ring where all processors (vertices) are totally indistinguishable except for their input value. Initially, to each vertex of the ring is associated a value from a totally ordered set; thus, forming a multiset. In this paper we consider the problem of sorting such a distributed multiset and we investigate its relationship with the election problem. We focus on the computability and the complexity of these problems, as well as on their interrelationship, providing strong characterizations, showing lower bounds, and establishing efficient upper bounds.

We consider the problem of adaptive fault diagnosis in hypercube multiprocessor systems. Processors perform tests on one another and later tests can be scheduled on the basis of previous test results. Fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. The goal is to identify correctly the status of all processors, assuming that the number of faults does not exceed the hypercube dimension. We propose an adaptive diagnosis algorithm whose efficiency is drastically better than that of any previously known strategies. While the worst-case number of tests for any of them exceeds 2/sup n/ log n for an n-dimensional hypercube, our method uses at most 2/sup n/+3n/2 tests in the worst case. We can also modify our algorithm to improve the number of testing rounds. By slightly increasing the number of tests to 2/sup n/+(n+1)/sup 2/ (still a much better performance than 2/sup n/ log n), we can carry out diagnosis in at most 11 rounds in the worst case (as opposed to over n rounds in the best previously known strategy).

We studied adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers give always correct test results, while faulty testers are completely unreliable. The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees,rings, and tori. These algorithms use the smallest possible number of tests in each case. Our results also imply optimal diagnosis for more general systems, assuming a small number of faults. The cost of adaptive diagnosis were found to be significantly smaller than that of classical (one-step) diagnosis. © 1999 John Wiley & Sons, Inc. Networks 34: 206–214, 1999

This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes are ranked by their adaptability, i.e., the maximum number of sites to be updated upon a topology change. An advantage of our scheme is that it implies a small number of updates upon a topology change. In particular, for the case of a bounded degree network it is proved that our scheme is optimal in its adaptability by presenting a matching tight lower bound. Our bubble routing scheme is a combination of a distributed routing database, a routing strategy, and a routing database update. It is shown how to perform the routing database update on a dynamic network in a distributed manner.

This paper identifies the equivalence of deadlock prevention in store-and-forward communication network and simultaneous arrival of packets to a switch of bufferless high-speed network. Scheduling of packet transmission schemes, which we call baked-potato schemes, are used to avoid simultaneous arrival of packets to a switch. We present scheduling schemes for any capacity of links and switches. The schemes are evaluated by the maximal length of time between two successive scheduling of a processor. For the case of single capacity link and switch, our scheme is proved optimal by presenting a matching lower bound. Our baked-potato scheme does not assume a prior knowledge on the source destination demands and can be used for sending control packets and broadcast. Research supported in part by NSERC (Natural Sciences and Engineering Research Council of Canada) grant. y Department of Mathematics and Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. Email: dolev@...

No abstract available.

We consider linear interval routing schemes studied by [3,5] from a graph-theoretical perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results of [3,5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish an Ω(n1/3) lower bound on the minimum number of intervals needed to achieve shortest path routings in the network considered.

This paper presents the first dynamic routing scheme for high-speed networks.The scheme is based on a hierarchical bubbles partition of the underlying communithat copym IS by perrmsslon of the Association of Computing Machinery.o cop otherwise, or to republish, requires y r a fee ancflor speci IC permission.

We consider true broadcast systems for the secure communication of session keys. These schemes provide for parallel rather than serial construction of broadcast messages, while avoiding selective broadcasting. We begin by introducing a conceptual framework for true broadcasting and illustrate its design with a secure key broadcast scheme based on probabilistic encryption. The framework provides for a system requiring user anonymity, as a result of the absence of addressing for the broadcast message. We also illustrate how Shamir's threshold scheme can be altered to allow for parallel broadcasting. We then present a formal model and use information theoretic techniques to establish a lower bound on the size of the broadcast message for a class of true broadcast schemes. Finally, we improve upon the aforementioned threshold scheme such that it achieves the lower bound.

This paper studies the invariance groups ${\bf S}(f)$ of boolean functions $f \in {\bf B}_n $ (i.e., $f:\{ 0,1\} ^n \to \{ 0,1\} $) on n variables, i.e., the set of all permutations on n elements which leave f invariant. After building intuition by presenting several examples that suggest relations between algebraic properties of groups and computational complexity of languages, necessary and sufficient conditions are given via Pólya’s cycle index for an arbitrary finite permutation group to be of the form $S(f)$, for some $f \in {\bf B}_n $. It is shown that asymptotically “almost all” boolean functions have trivial invariance groups. For cyclic groups $G \leqq {\bf S}_n $ a logspace algorithm for determining whether the given group is of the form ${\bf S}(f)$, for some $f \in {\bf B}_n $ is given. The applicability of group theoretic techniques in the study of the parallel complexity of languages is demonstrated. For any language L let $L_n $ be the characteristic function of the set of all strings in L which have length exactly n and let ${\bf S}_n (L)$ be the invariance group of $L_n $. The index $| {{\bf S}_n :{\bf S}_n (L)} |$ are considered as a function of n and the class of languages whose index is polynomial in n is studied. Bochert’s lower bound on the index of primitive permutation groups is used together with the O’Nan-Scott theorem, a deep result in the classification of finite simple groups, in order to show that any language with polynomial index is in (nonuniform) ${\text{TC}}^0 $ and hence in (nonuniform) ${\text{NC}}^1 $. As a corollary, an extension is given of a result of Fagin–Klawe-Pippenger–Stockmeyer, giving necessary and sufficient conditions for a language with polynomial index to be computable by a constant depth polynomial size circuit family. As another corollary, it is shown that the problem of “weight-swapping” for a sequence of groups of polynomial index is in (nonuniform) ${\text{NC}}^1 $.

We study enumeration and visibility problems in the d-dimensional integer lattice Ldn of d-tuples of integers ≤ n. In the first part of the paper we give several useful enumeration principles and use them to study the asymptotic behavior of the number of straight lines traversing a certain fixed number of lattice vertices of Ldn, the line incidence problem and the edge visibility region. In the second part of the paper we consider an art gallery problem for point obstacles. More specifically we study the camera placement problem for the infinite lattice Ld. A lattice point is visible from a camera C (positioned at a vertex of Ld) if the line segment joining A and C crosses no other lattice vertex. For any given number s ≤ 3d of cameras we determine the position they must occupy in the lattice Ld in order to maximize their visibility.

Abstract Several stepping up lemmas are proved which are then used to investigate the connection between definable partition relations and admissible ordinals.