Abstract. We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then there is a complete characterization that was established more than 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analyzing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.

Necessary and sufficient conditions for a pair of integer sequences to be the degree sequences of the two sides of a bipartite graph were established more than six decades ago by Gale and Ryser. In contrast, the general question of deciding whether a single sequence is bigraphic, namely, can be realized by a bipartite graph, is still open. We consider even sequences, in which the multiplicity of any integer in the degree sequence is even. One can always partition an even sequence into two identical sequences, resulting in an equal partition. We show that if a given even sequence d is graphic, then there are only two options: either d is bigraphic, or d is 2-bigraphic, namely, can be realized by a bipartite multigraph with maximum multiplicity 2. For an r -graphic sequence we show that it is t -bigraphic for some t ≤ 2 r , and we also show that the analysis is tight, namely that t = 2 r is possible. In addition, we show that given an r -graphic sequence d , there exists an even sequence d ′ which is similar to d in a well-defined sense such that d ′ is even and r -graphic, and therefore t -bigraphic for some t ≤ 2 r .

A sequence d = (d_1,d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding.

The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.

We consider the problem of realizable interval sequences. An interval sequence is comprised of $n$ integer intervals $[a_i,b_i]$ such that $0\le a_i\leq b_i \le n-1$ and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n),$ satisfying the condition $a_i\leq d_i\leq b_i$ for each $i\in[1,n]$. There is a characterization (also implying an $O(n)$ verifying algorithm) known for realizability of interval sequences, which is a generalization of the Erdös--Gallai characterization for graphic sequences. However, given any realizable interval sequence, there is no known algorithm for computing a corresponding graphic certificate in $o(n^2)$ time. In this paper, we provide an $O(n \log n)$ time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is nonrealizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence in the same time. Finally, we consider variants of the problem, such as computing the most-regular graphic sequence and computing a minimum extension of a length $p$ nongraphic sequence to a graphic one.

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

We study the maximum size of coverage gaps by sensors selected to cover a path. Gap sizes, and not just total coverage, are important because significant events can be missed during uncovered periods. The amount of knowledge about a path affects the ability to select sensors to cover it. We first study how coverage gaps are affected by increases in knowledge and improvements in selection strategies when sensors are selected to maximize path coverage. The gap size does not necessarily decrease in the same way that coverage increases with a better selection. We then show that even simple modifications to the algorithm can reduce the coverage gap, and show how this is affected about the level of knowledge.

We study how knowledge of a moving object's path can be used to select sensors in a network that maximize the coverage of its path. We propose a mobility model that combines the shortest path between two points with random movement. Given the mobility model, we have different knowledge levels in terms of knowing nothing, the start, destination, movement model, and the whole path. We present a framework to assign weights to points on the movement grid based on the knowledge level and to greedily select sensors to maximize weighted coverage of the grid. We show in simulations of random movement that knowing more information generally has better performance, but for certain levels of knowledge, this decreases as the randomness increases. We also find that it is possible to obtain the maximum coverage by assuming the target follows the shortest path when the randomness is below a certain threshold. We verified these results on real human mobility traces.

We consider sensor selection to optimize multiple conditions. Specifically, we model the sensor network as a graph, in which weighted edges indicate the ability of one node to predict the data of another. Each node is associated with several data types, so there are links for each data type. The objective is to maximize the coverage of all data types. This is applicable to such problems as monitoring air quality in cities and coal mines using several indicators of quality. We first define the maximization criteria, and then how to modify the model and existing algorithms to solve the problem. We demonstrate the importance of the problem and the quality of our methodology on synthetic and realistic scenarios.

This paper introduces a novel paradigm for resource management in distributed systems, called decision-driven execution. The paradigm is appropriate for mission-driven systems, where the goal is to enable faster, leaner, and more effective decision making. All resource consumption, in this paradigm, is tied to the needs of making decisions on alternative courses of action. A point of departure from traditional architectures lies in interfaces that allow applications to specify their underlying decision logic. This specification, in turn, allows the system to reason about most effective means to meet information needs of decisions, resulting in simultaneous optimization of decision accuracy, cost, and speed. The paper discusses the overall vision of decision-driven execution, outlining preliminary work and novel challenges.

Sensor networks and the Internet of Things motivate novel classes of job scheduling problems where each "job" corresponds to downloading some data object from the sensor network, i.e., querying the network for some portion of its current state. The purpose of scheduling a set of jobs may be to support decision tasks, where the user will make a choice, prior to a deadline, informed by all the data obtained about the current situation or state. Because different aspects of the state will tend to change over time, rendering previously downloaded measurements of them "stale", we want all the data jobs to be still fresh when the last one completes. This leads to scheduling constraints much more complex than simply meeting a deadline. We investigate such freshness scheduling problems under several scenarios. We give a polynomial-time optimal algorithm for the problem of maximizing the (weighted) number of jobs scheduled via a single download channel, and an O(log n)- approximation algorithm for the (NP-hard) problem of scheduling all jobs via a minimum number of channels. The optimal algorithm exploits a shared structure between (single-deadline) freshness scheduling and ordinary scheduling with jobs-specific deadlines. Finally, we compare our approximation algorithm with natural heuristics in simulation.

Sensor networks are ubiquitously used for detection and tracking and, as a result, covering is one of the main tasks of such networks. We study the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery power, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. Sensors are first deployed and then coverage commences. Energy is consumed in proportion to the distance traveled for mobility, while for coverage, energy is consumed in direct proportion to the radius of the sensor raised to a constant exponent. We study two variants which are distinguished by whether the sensing radii are given as part of the input or can be optimized: the fixed radii problem and the variable radii problem. We design parametric search algorithms for both problems for the case where the final order of the sensors is predetermined (e.g., sensors cannot swap locations and the initial order must be preserved) and for the case where sensors are initially located at barrier endpoints. In contrast, we show that the variable radii problem is strongly NP-hard and provide hardness of approximation results for fixed radii for the case where all the sensors are initially colocated at an internal point of the barrier.

We consider the network-wide broadcast problem in multihop wireless networks with reliable multicast at the Medium Access Control (MAC) layer, where the cost of transmitting to downstream nodes at each branch point in the broadcast tree depends on the number$k$of recipients, specifically$1+A k^b$in our model (for some$b \geq 0$,$A \geq 0$). This allows us to capture a wide array of MAC-layer approaches and their costs, simply by varying the value of$b$(relative to$A$), in a problem formulation subsuming the Connected Dominating Set and Spanning Tree problems. We give a systematic analysis of this problem, including positive and negative results. In particular, we show the problem is: approximable by a factor varying from$2H_{\Delta}+2$down to 2 as$b$varies from 0 to 1 (where$\Delta$is the maximum degree of the network graph and$H_\Delta$is the$\Delta$th harmonic number); approximable by a factor varying from 2 to 1 (i.e., optimal) as$b$varies from 1 to$\log _2 (\frac{1}{A}+2)$; and optimally solvable thereafter. Finally, we present numerical results comparing the two algorithms above with other natural heuristics. We find there is an advantage in algorithms taking into consideration the value$b$, even if$b$can only be roughly estimated.

The paper considers the challenge of maximizing the quality of information collected to meet decision needs of real-time Internet-of-Things applications. A novel scheduling model is proposed, where applications need multiple data items to make decisions, and where individual data items can be captured at different levels of quality. We assume the existence of a single bottleneck over which data objects are collected and schedule the transmission of these objects over the bottleneck to meet decision deadlines and data validity constraints, while maximizing quality. A family of heuristic algorithms is presented to solve this problem. Their performance is empirically compared leading to insights into the solution space.

The Internet of Things heralds a new generation of data-centric applications, where controllers connect to large numbers of heterogeneous sensing devices. We consider a model, where the control loop does not execute periodically. Instead, controllers are prompted by contextual cues to make one-off decisions, resulting in sporadic activations. Since the need for data arises only sporadically, sensors do not sample data continuously. Rather, they are normally off (e.g., to save energy), but are activated by the controller on demand, when data is needed. Collected data has validity intervals, after which it must be re-sampled, since the measured value may change. Once a decision is made based on the data, sensors are turned off again. We call this model sporadic decision-centric data scheduling with normally-off sensors. It gives rise to novel scheduling problems because of the way the timing of activation of different sensors affects load attributed to data sampling; the shorter the interval between activation of a given sensor and the time a corresponding decision is made, the lower the number of samples taken by that sensor to support the decision, and thus decision cost. The paper defines the aforementioned decision-centric data scheduling problem and derives the optimal scheduling policy, called EDEF-LVF, for this task model. Simulation results confirm the superiority of EDEF-LVF compared to several baselines.

In an ever-increasing variety of contexts, people are working collaboratively to solve problems and accomplish tasks. Yet the characteristics of teams that work effectively are not fully understood. We focus on the problem of identifying particularly effective teams in a large, complex, social network. More specifically, given some task, and taking into account measures of both the effectiveness of an individual and the strength of the pairwise ties between individuals, can we identify the subgroup of people who are most likely to accomplish said task? Our experimental work using the DBLP suggests that within any given subgroup, not all ties are of equal relevance. In fact, we show that focusing on the ties between one individual and the other group members will suffice. However, whereas the problem of finding the "best" subgroup is equivalent to MAX-CLIQUE and is thus hard to approximate, the problem of finding the best star is computationally tractable. We present experimental evidence justifying interest in the star, as opposed to the clique, and discuss algorithmic and complexity concerns.

An important problem in the study of sensor networks is how to select a set of sensors that maximizes coverage of other sensors. Given pair wise coverage values, three commonly found functions give some estimate of the aggregate coverage possible by a set of sensors: maximum coverage by any selected sensor (MAX), total coverage by all selected sensors (SUM), and the probability of correct prediction by at least one sensor (PROB). MAX and SUM are two extremes of possible coverage, while PROB, based on an independence assumption, is in the middle. This paper addresses the following question: what guarantees can be made of coverage that is evaluated by an unknown sub-modular function of coverage when sensors are selected according to MAX, SUM, or PROB? We prove that the guarantees are very bad: In the worst case, coverage differs by a factor of sqrt(n), where n is the number of sensors. We show in simulations on synthetic and real data that the differences can be quite high as well. We show how to potentially address this problem using a hybrid of the coverage functions.

The paper describes a novel algorithm for timely sensor data retrieval in resource-poor environments under freshness constraints. Consider a civil unrest, national security, or disaster management scenario, where a dynamic situation evolves and a decision-maker must decide on a course of action in view of latest data. Since the situation changes, so is the best course of action. The scenario offers two interesting constraints. First, one should be able to successfully compute the course of action within some appropriate time window, which we call the decision deadline. Second, at the time the course of action is computed, the data it is based on must be fresh (i.e., within some corresponding validity interval). We call it the freshness constraint. These constraints create an interesting novel problem of timely data retrieval. We address this problem in resource-scarce environments, where network resource limitations require that data objects (e.g., pictures and other sensor measurements pertinent to the decision) generally remain at the sources. Hence, one must decide on (i) which objects to retrieve and (ii) in what order, such that the cost of deciding on a valid course of action is minimized while meeting data freshness and decision deadline constraints. Such an algorithm is reported in this paper. The algorithm is shown in simulation to reduce the cost of data retrieval compared to a host of baselines that consider time or resource constraints. It is applied in the context of minimizing cost of finding unobstructed routes between specified locations in a disaster zone by retrieving data on the health of individual route segments.

A hypergraph is a set V of vertices and a set of nonempty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for random geometric hypergraphs, energy efficient routing in multichannel multiradio networks, and the Enron email data set. The experiment with the Enron email data set illustrates the application of the proposed algorithms in social networks for identifying the most important actor and the latent social relationship based on the closeness centrality metric.

This paper complements the large body of social sensing literature by developing means for augmenting sensing data with inference results that "fill-in" missing pieces. Unlike trend-extrapolation methods, we focus on prediction in disaster scenarios where disruptive trend changes occur. A set of prediction heuristics (and a standard trend extrapolation algorithm) are compared that use either predominantly-spatial or predominantly-temporal correlations for data extrapolation purposes. The evaluation shows that none of them do well consistently. This is because monitored system state, in the aftermath of disasters, alternates between periods of relative calm and periods of disruptive change (e.g., aftershocks). A good prediction algorithm, therefore, needs to intelligently combine time-based data extrapolation during periods of calm, and spatial data extrapolation during periods of change. The paper develops such an algorithm. The algorithm is tested using data collected during the New York City crisis in the aftermath of Hurricane Sandy in November 2012. Results show that consistently good predictions are achieved. The work is unique in addressing the bi-modal nature of damage propagation in complex systems subjected to stress, and offers a simple solution to the problem.

Timely and efficient message transmission through intermittently and sparsely connected networks is a problem of significant interest to the mobile networking community. Although the long-term statistics describing the time-varying connectivity in such networks can be characterized systematically and can be used for selecting good routes, it may be possible to achieve better performance by intelligently using the actual link states at the time of routing, in conjunction with these statistical dynamics models. In this paper, we investigate a family of minimum expected latency routing methods for such dynamic networks, spanning purely model-based and state-oblivious source routing, state-based source routing, and various flavors of dynamic (or hop-by-hop) routing, with increasing amounts of current link state knowledge around the source. First, we give a heuristic and an approximation scheme for the model-assisted source routing problem, as well as heuristics for the dynamic routing problem. Then we show using extensive simulations on both synthetic and real time-varying connectivity traces that although dynamically sampling link states helps to improve expected routing latency compared to source routing, the marginal improvements decline rapidly for knowledge of current link states beyond 2 hops. To the best of our knowledge, this is the first thorough characterization of the performance of the entire spectrum of model-assisted routing algorithms ranging from little knowledge to complete knowledge of link dynamics.

Time-varying graphs (T-graph) consist of a time-evolving set of graph snapshots (or graphlets). A T-graph property with potential applications in both computer and social network forensics is T-reachability, which identifies the nodes reachable from a source node using the T-graph edges over time period T. In this paper, we consider the problem of estimating the T-reachable set of a source node in two different settings - when a time-evolution of a T-graph is specified by a probabilistic model, and when the actual T-graph snapshots are known and given to us offline (“data aware” setting). Since the value of T could be large in many applications, we propose two simple techniques, namely T-graph sampling and T-graph smashing for significantly reducing the complexity of this computation, while minimizing the estimation error. We show that for the data-aware case, both T-graph sampling and smashing problems are NP-hard, but they are amenable to reasonably good approximations. We also show that for the probabilistic setting where each graphlet in a T-graph is an Erdos-Renyi random graph, sampling yields a loose lower bound for the T-reachable set, while different styles of smashing yield more useful upper and lower bounds. Finally, we show that our algorithms (both data-aware and data-oblivious) can estimate the T-reachable set in real world time-varying networks within reasonable accuracy using less than 0.5% of the number of graphlets.

In social swarming applications, participants equipped with 3G and WiFi-capable smartphones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: Each report has an associated deadline, and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible; in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations and experiments on an Android-based implementation, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal.

We study a data dissemination scenario in which data items are to be transmitted to mobile clients via one of the stationary data access points (APs) that the clients pass by en route to their destinations. The scheduler dedicates sequences of consecutive timeslots of an AP to downloading a data item to a client during the time window in which it is in range, which corresponds to assigning a job (the client's download) to a machine (the AP) among many. The transmission rate chosen for each assignment partly corresponds to setting a machine's speed, but it also has subtler effects. The APs may control transmission power to tune its transmission range making sure that no interference occurs with neighboring APs' transmissions. The problem is a generalization of an already NP-hard parallel-machine scheduling problem in which jobs' release times and deadlines depend on the machine to which they are assigned. We define this joint timeslot, power control, and rate assignment problem formally and apply both new algorithms and adaptations of existing algorithms to it. We evaluate these algorithms through simulations which show that our proposed algorithms achieve near-optimal throughput.

Motivated by an availability gap for visual media, where images and videos are uploaded from mobile devices well after they are generated, we explore the selective, timely retrieval of media content from a collection of mobile devices. We envision this capability being driven by similarity-based queries posed to a cloud search front-end, which in turn dynamically retrieves media objects from mobile devices that best match the respective queries within a given time limit. Building upon a crowd-sensing framework, we have designed and implemented a system called MediaScope that provides this capability. MediaScope is an extensible framework that supports nearest-neighbor and other geometric queries on the feature space (e.g. clusters, spanners), and contains novel retrieval algorithms that attempt to maximize the retrieval of relevant information. From experiments on a prototype, MediaScope is shown to achieve near-optimal query completeness and low to moderate overhead on mobile devices.

Motivated by an availability gap for visual media, where images and videos are uploaded from mobile devices well after they are generated, we explore the selective, timely retrieval of media content from a collection of mobile devices.

We model the problem of channel assignment in mobile networks as one of temporal coloring (T-coloring), that is, coloring a time-varying graph. In order to capture the impact of channel re-assignments due to mobility, we model the cost of coloring as C + αA, where C is the total number of colors used and A is the total number of color changes, and α is a user-selectable parameter reflecting the relative penalty of channel usage and re-assignments.

In this demo, a learning system, called Metis, is presented that extrapolates missing pieces in participatory sensing data. The work addresses the challenge of incomplete coverage in participatory sensing applications, where lack of complete control over participant mobility and sensing patterns may create coverage gaps in space and in time. Metis learns the underlying spatiotemporal patterns of the measured phenomenon from available incomplete observations, and uses these patterns to infer missing data. We describe the overall system design and demonstrate the system using data collected during the New York City gas crisis in the aftermath of Hurricane Sandy.

In the Set Once Strip Cover problem n wireless sensors are deployed over a one-dimensional region. Each sensor has a battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The problem is to find an assignment of radii and activation times that maximizes the length of time during which the entire region is covered. We show that this problem is NP-hard. We also show that the approximation ratio of Round Robin, the algorithm in which the sensors take turns covering the entire region, is 3/2 in both Set Once Strip Cover and the more general Strip Cover problem, in which each radius may be set finitely-many times. Moreover, we show that the more general class of duty cycle algorithms, in which groups of sensors take turns covering the entire region, can do no better. Finally, we give an polynomial time algorithm that solves the related Set Radius Strip Cover problem, in which sensors must be activated immediately.

We study a data dissemination scenario in which data items are to be transmitted to mobile clients via one of the stationary data access points (APs) that the clients pass by en route to their destinations. The scheduler dedicates sequences of consecutive timeslots of an AP to downloading a data item to a client during the time window in which it is in range, which corresponds to assigning a job (the client's download) to a machine (the AP) among many. The transmission rate chosen for each assignment partly corresponds to setting a machine's speed, but it also has subtler effects. The APs may control transmission power to tune its transmission range making sure that no interference occurs with neighboring APs' transmissions. The problem is a generalization of an already NP-hard parallel-machine scheduling problem in which jobs' release times and deadlines depend on the machine to which they are assigned. We define this joint timeslot, power control, and rate assignment problem formally and apply both new algorithms and adaptations of existing algorithms to it. We evaluate these algorithms through simulations which show that our proposed algorithms achieve near-optimal throughput.

In social swarming applications, participants equipped with 3G and WiFi-capable smart phones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: each report has an associated deadline and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports, but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible: in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations with real-world measurements, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal.

As sensor mobility becomes more and more universal, Wireless Sensor Network (WSN) configurations that utilize such mobility will become the norm. We consider the problem of maximizing the lifetime of a wireless connection between a transmitter and a receiver using mobile relays. Initially, all relays are positioned arbitrarily on the line between the transmitter and the receiver and have arbitrary battery capacities. Energy is consumed in proportion to the distance traveled for mobility and in proportion to an exponential function of the distance over which information is sent for communication. Relays can move to different locations as long as they have the energy to do so. The objective is to find positions and thus transmission ranges for the nodes that maximize the lifetime of the network. We study two models. The first is more restrictive, and corresponds to the case where relays are allowed to be set once at time zero (single deployment), while the second model corresponds to the case where relays can be adjusted multiple times (multiple deployments). We show how to compute an optimal solution for the case of no movement cost for both models. We consider a discrete version of the single deployment model, in which relays must be deployed on grid points. We provide two algorithms for this case: a dynamic programming algorithm and a binary search algorithm on potential lifetimes. We prove that both algorithms are FPTASs for the non-discrete problem, if batteries are not too small. Based on these algorithms and on additional ideas we develop a number of heuristics for the multiple deployments model. We evaluate them using simulations and compare them with the lower bound of relays not moving at all and the upper bound of cost-free movement. Our simulations - across a range of mobility and transmission costs, sensible starting locations and battery capacities - demonstrate the benefit of moving over remaining at initial locations even for single deployment.

Data-gathering or convergecast problems have traditionally been studied in two combinations of settings: one-shot scheduling of data items with no aggregation, and periodic scheduling of data items with full aggregation meaning that any number of unit-size data items can, if available, be aggregated into a single (unit-size) data item (e.g., by summing or averaging values). In this paper, we extend beyond these problem settings in two ways. First, we study a) one-shot throughput maximization in settings with aggregation and b) periodic scheduling in settings without aggregation. Second, we generalize the notion of aggregatability in both one-shot and periodic scheduling beyond the binary choice of either all sets of items being aggregatable or none being so. Modeling the presence of multiple semantic data types (e.g., target counts to be summed and temperature readings to be averaged), we partition data items into classes, whereby items are aggregatable if they belong to the same class, in both periodic and non-periodic settings. For these two problems we provide guaranteed approximations and heuristics, for a variety of general and special cases. We then evaluate the algorithms in a systematic simulation study, both under the conditions in which our provable guarantees apply and in more general settings, where we find the algorithms continue to perform well on typical problem inputs.

We consider variations of a problem in which data must be delivered to mobile clients en route, as they travel toward their destinations. The data can only be delivered to the mobile clients as they pass within range of wireless base stations. Example scenarios include the delivery of building maps to firefighters responding to multiple alarms. We cast this scenario as a parallel-machine scheduling problem with the little-studied property that jobs may have different release times and deadlines when assigned to different machines. We present new algorithms and also adapt existing algorithms, for both online and offline settings. We evaluate these algorithms on a variety of problem instance types, using both synthetic and real-world data, including several geographical scenarios, and show that our algorithms produce schedules achieving near-optimal throughput.

Positioning disk-shaped sensors to optimize certain coverage parameters is a fundamental problem in ad hoc sensor networks. The hexagon lattice arrangement is known to be optimally efficient in the plane, even though 20.9% of the area is unnecessarily covered twice, however, the arrangement is very rigid—any movement of a sensor from its designated grid position (due to, e.g., placement error or obstacle avoidance) leaves some region uncovered, as would the failure of any one sensor. In this article, we consider how to arrange sensors in order to guarantee multiple coverage, that is, k -coverage for some value k > 1. A naive approach is to superimpose multiple hexagon lattices, but for robustness reasons, we may wish to space sensors evenly apart. We present two arrangement methods for k -coverage: (1) optimizing a Riesz energy function in order to evenly distribute nodes, and (2) simply shrinking the hexagon lattice and making it denser. The first method often approximates the second, and so we focus on the latter. We show that a density increase tantamount to k copies of the lattice can yield k ′-coverage, for k ′ > k (e.g., k = 11, k ′ = 12 and k = 21, k ′ = 24), by exploiting the double-coverage regions. Our examples' savings provably converge in the limit to the ≈ 20.9% maximum. We also provide analogous results for the square lattice and its ≈ 57% inefficiency (e.g., k = 3, k ′ = 4 and k =5, k ′ = 7) and show that for multi-coverage for some values of k ′, the square lattice can actually be more efficient than the hexagon lattice. We also explore other benefits of shrinking the lattice: Doing so allows all sensors to move about their intended positions independently while nonetheless guaranteeing full coverage and can also allow us to tolerate probabilistic sensor failure when providing 1-coverage or k -coverage. We conclude by construing the shrinking factor as a budget to be divided among these three benefits.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications: search and rescue, coordinated fire-fighting, and the DARPA balloon hunt challenge. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event. We first propose a model, based on common notions of believability, about the credibility of information. We then cast the problem posed above as a discrete optimization problem, prove hardness results, introduce optimal centralized solutions, and design an approximate solution amenable to decentralized implementation whose performance is about 20 percent off, on average, from the optimal (on real-world data sets derived from Google News) while being three orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions. To our knowledge, we are the first to propose and explore the problem of extracting credible information from a network of smartphones.

We introduce the pan and scan problem, in which cameras are configured to observe multiple target locations. This is representative example within a broad family of problems in which multiple sensing devices are deployed, each in general observing multiple targets. A camera's configuration here consists of its orientation and its zoom factor or field of view (its position is given); the quality of a target's reading by a camera depends (inversely) on both the distance and field of view. After briefly discussing an easy setting in which a target accumulates measurement quality from all cameras observing it, we move on to a more challenging setting in which for each target only the best measurement of it is counted. Although both variants admit continuous solutions, we observe that we may restrict our attention to solutions based on pinned cones. For a geometrically constrained setting, we give an optimal dynamic programming algorithm. For the unconstrained setting of this problem, we prove NP-hardness, present efficient centralized and distributed 2-approximation algorithms, and observe that a PTAS exists under certain assumptions. For a synchronized distributed setting, we give a 2-approximation protocol and a (2β)/(1 - α)-approximation protocol (for all 0 ≤ α ≤ 1 and β >; 1, though satisfying these constraints with equality will in different ways trivialize the guarantees) with the stability feature that no target's camera assignment changes more than logβ(m/α) times. We also discuss the running times of the algorithms and study the speed-ups that are possible in certain situations.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event? We first propose a model, based on common intuitions of believability, about the credibility of information. We then cast the problem as a discrete optimization problem, and introduce optimal centralized solutions and an approximate solution amenable to decentralized implementation whose performance is about 20% off on average from the optimal while being 3 orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions.

We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total broadcast cost, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. These two algorithms offer tradeoffs between performance and time complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem.

In a composite network, a piece of information traveling through links in a social network may have to travel over multiple links in an associated communication network. In this paper, we propose a model of composite networks that consists of two networks and an embedding between them, and several composite metrics that characterize information flow under a particular type of embedding. We present analytic results for the scaling behavior of "constrained composite stretch" of a path, "constrained composite diameter" of a graph, and "constrained composite broadcast time" of a tree, under random uniform embeddings onto various communication network structures. We validate our analytical results on composite stretch using two data sets consisting of a friendship social network geographically spread across Western Europe and a historical deployment of a military chain of command. We also present a randomized model of field deployment consistent with real-world data, and use simulations over this model to explore the distribution of constrained composite broadcast time. Finally, we show that our analytical bounds for composite broadcast time agree well with the simulation results.

We study a problem in which a single sensor is scheduled to observe sites periodically, motivated by applications in which the goal is to maintain up-to-date readings for all the observed sites. In the existing literature, it is typically assumed that the time for a sensor switching from one site to another is negligible. This may not be the case in applications such as camera surveillance of a border, however, in which the camera takes time to pan and tilt to refocus itself to a new geographical location. We formulate a problem with refocusing delay constraints. We prove the problem to be NP-hard and then study a special case in which refocusing is proportional to some Euclidian metric. We give a lower bound on the optimal cost for the scheduling problem. Finally, we provide and experimentally evaluate several heuristic algorithms, some of them based on this computed lower bound.

A token is hidden in one of several boxes and then the boxes are locked. The probability of placing the token in each of the boxes is known. A searcher is looking for the token by unlocking boxes where each box is associated with an unlocking cost. The searcher conducts its search in rounds and must find the token in a predetermined number of rounds. In each round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is to minimize the expected cost of unlocking boxes until the token is found. The motivation and main application of this game is the task of paging a mobile user (token) who is roaming in a zone of cells (boxes) in a cellular network system. Here, the unlocking costs reflect cell congestions and the placing probabilities represent the likelihood of the user residing in particular cells. Another application is the task of finding some data (token) that may be known to one of the sensors (boxes) of a sensor network. Here, the unlocking costs reflect the energy consumption of querying sensors and the placing probabilities represent the likelihood of the data being found in particular sensors. In general, we call mobile data any entity that has to be searched for.

We introduce the pan and scan problem, in which cameras are configured to observe multiple target locations. A camera's configuration consists of its orientation and its zoom factor or field or view (its position is given); the quality of a target's reading by a camera depends (inversely) on both the distance and field of view.

When a sensor network is deployed, it is typically required to support multiple simultaneous missions. Schemes that assign sensing resources to missions thus become necessary. In this article, we formally define the sensor-mission assignment problem and discuss some of its variants. In its most general form, this problem is NP-hard. We propose algorithms for the different variants, some of which include approximation guarantees. We also propose distributed algorithms to assign sensors to missions which we adapt to include energy-awareness to extend network lifetime. Finally, we show comprehensive simulation results comparing these solutions to an upper bound on the optimal solution.

When a sensor network is deployed in the field it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we consider new sensor-assignment problems motivated by frugality, i.e., the conservation of resources, for both static and dynamic settings. In the most general setting, the problems we study are NP-hard even to approximate, and so we focus on heuristic algorithms that perform well in practice. In the static setting, we propose a greedy centralized solution and a more sophisticated solution that uses the Generalized Assignment Problem model and can be implemented in a distributed fashion. In what we call the dynamic setting, missions arrive over time and have different durations. For this setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We find that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help, making this decision based on the value of the mission, the sensor's remaining energy, and (if known) the remaining target lifetime of the network. Finally, we evaluate our solutions through simulations.

Positioning disk-shaped sensors to optimize certain coverage parameters is a fundamental problem in ad-hoc sensor networks. The hexagon grid lattice is known to be optimally efficient, but the 20.9% of the area covered by two sensors may be considered a waste. Furthermore, any movement of a sensor from its designated grid position or sensor failure, due to placement error or obstacle avoidance, leaves some region uncovered, as would the failure of any one sensor. We explore how shrinking the grid can help to remedy these shortcomings. First, shrinking to obtain a denser hexagonal lattice allows all sensors to move about their intended positions independently while nonetheless guaranteeing full coverage. Second, sufficiently increasing the lattice density will naturally yield k-coverage for k > 1. Moreover, we show that a density increase tantamount to fc copies of the lattice can yield k' -coverage, for kj> k (e.g. k = 11, kj= 12), through the exploitation of the double-coverage regions. Our examples' savings provably converge in the limit to the ap 20.9% maximum. We also provide analogous results for the square lattice and its ap 57% inefficiency, including k = 3, kj= 4, k = 5,kj= 7, indicating that for multi-coverage, the square lattice can actually be more efficient than the hexagon lattice. All these efficiency gains can be used to provide 1-coverage or fc-coverage even in the face of probabilistic sensor failure. We conclude by construing the shrinking factor as a budget to be divided among these three benefits.

We consider a sensor network placement problem where the sensing range of a sensor depends on its location in order to model the effect of terrain features. We study how sensors should be placed in order to maximize the coverage and illustrate how digital halftoning algorithms from the field of image processing can be useful in this respect. In particular, we reduce the sensor placement problem to a corresponding image halftoning problem and then apply two well known halftoning algorithms to the problem: dither mask halftoning and direct binary search. We illustrate our approach with experimental results and show that this approach is also applicable to the problem of preferential coverage.

We consider variations of a problem in which data must be delivered to mobile clients en-route, as they travel towards their destinations. The data can only be delivered to the mobile clients as they pass within range of wireless base stations. Example scenarios include the delivery of building maps to firefighters responding to multiple alarms, and the in-transit ldquoilluminationrdquo of simultaneous surface-to-air missiles. We cast this scenario as a parallel-machine scheduling problem with the little-studied property that jobs may have different release times and deadlines when assigned to different machines. We present new algorithms and also adapt existing algorithms, for both online and offline settings. We evaluate these algorithms on a variety of problem instance types, using both synthetic and real-world data, including several geographical scenarios, and show that our algorithms produce schedules achieving near-optimal throughput.

In many situations it is important to deliver information to personnel as they work in the field. We consider such a specialized content distribution application in wireless mesh networks. When a new mission arrives-for example, when an alarm for a fire is reported-data is pushed to storage nodes at the mission site where it may be retrieved locally by responding personnel (e.g., police, firefighters, paramedics, government officials, and the media). It is important that information is available at low latency, when requested or pulled by the personnel. The total latency experienced will be a combination of the push delay (if the personnel arrive at the mission site before all the data can be pushed), and the pull delay. Each delay component will in turn be a function of 1) the hop distance traveled by the data when pushed or pulled and 2) the congestion on the links. In this paper, we define algorithms and protocols that trade-off the push and pull latencies depending on the type of application. Our goal is to choose a storage node assignment minimizing the total latency-based cost. We start with a simple model in which cost is a function of distance, and then extend the model explicitly taking congestion into account. Since the problem is NP-hard to approximate, our focus is on developing efficient algorithms and distributed protocols that can be easily deployed in wireless mesh networks. In NS2 simulations, we find that our heuristic algorithms achieve on average a cost within at most 15 % of the optimum.

We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.

When a sensor network is deployed in the field, it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we propose centralized and distributed schemes to assign sensors to missions. We also adapt our distributed scheme to make it energy-aware to extend network lifetime. Finally, we show simulation results comparing these solutions. We find that our greedy algorithm frequently performs near-optimally and that the distributed schemes usually perform nearly as well.

An ad-hoc sensor network is composed of sensing devices which can measure or detect features of their environment, communicate with one other and possibly with other devices that perform data fusion. One of the problems motivated by ad-hoc sensor networks is to position sensors in order to maximize coverage, or equivalently to minimize the number of sensors required to cover a given area.

In sensor networks applied to monitoring applications, individual sensors may perform preassigned or on-demand tasks, or missions. Data updates (info-pages) may be sent to sensors from a command center, via a time-division broadcast channel. Sensors are normally put in sleep mode when not actively listening, in order to conserve energy in their batteries. Hence, a schedule is required that specifies when sensors should listen for updates and when they should sleep. The performance of such a schedule is evaluated based on data-related costs and sensor-related costs. Data-related costs reflect the obsoleteness of current sensor data, or the delay while sensors wait for updated instructions. Sensor-related costs reflect the energy that sensors consume while accessing the broadcast channel and while switching between the active and sleeping modes (rebooting). Our goal is a schedule with the minimum total cost. Previous related work has explored data-related costs, but listening cost has been addressed only under the assumption that the rebooting operation is free. This paper formulates a new cost model, which recognizes the cost of sensor rebooting. We derive an optimal schedule for the single-sensor setting. We proceed to consider schedules of multiple sensors, and formulate a mathematical program to find an optimal fractional schedule for this setting. Several heuristics for scheduling multiple sensors are introduced and analyzed, and various tradeoffs among the cost factors are demonstrated.

We investigate deterministic algorithms for a frequency assignment problem in cellular networks. The problem can be modeled as a special vertex coloring problem for hypergraphs: In every hyperedge there must exist a vertex with a color that occurs exactly once in the hyperedge (the conflict-free property). We concentrate on a special case of the problem, called conflict-free coloring for intervals. We introduce a hierarchy of four models for the aforesaid problem: (i) static, (ii) dynamic offline, (iii) dynamic online with absolute positions, and (iv) dynamic online with relative positions. In the dynamic offline model, we give a deterministic algorithm that uses at most log 3/2 n + 1 ≈ 1.71 log 2 n colors and show inputs that force any algorithm to use at least 3 log 5 n + 1 ≈ 1.29 log 2 n colors. For the online absolute-positions model, we give a deterministic algorithm that uses at most 3⌈log 3 n ⌉ ≈ 1.89 log 2 n colors. To the best of our knowledge, this is the first deterministic online algorithm using O (log n ) colors in a nontrivial online model. In the online relative-positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the first-fit greedy online algorithm. We also consider conflict-free coloring only with respect to intervals that contain at least one of the two extreme points.

A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it never reports its location unless it leaves the zone. The N cells are associated with a probability vector (p1, ...,pN) where piis the probability that the mobile user resides in the ith cell and all the probabilities are independent. A delay constraint paging strategy must find the mobile user within D (1 les D les N) paging rounds; in each round a subset of the N cells is paged. The goal is to minimize the expected number of paged cells until the mobile user is found. Solutions based on dynamic programming that yield optimal strategies are known. The running time of the known implementations is Theta(N2D). Our first contribution is to improve the running time to Theta(ND) by proving that the dynamic programming recursive formulation satisfies the Monge property, permitting us to use various dynamic programming speedup techniques. A Theta(N) heuristic solution is also known. Our second contribution is a heuristic whose running time is Theta(N log D). Our heuristic outperforms the known heuristic while running faster for D << N. We compare the non-optimal heuristics with the optimal solution demonstrating the tradeoff between optimality and running time efficiency of various solutions.

No abstract available.

Given is a sequence of n positive integers w 1 , w 2 ,…, w n that are associated with the items 1,2,… n , respectively. In the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most w i slots (a slot is the transmission time of one page). In the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/ w i . The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/ w i of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing. Let H = ⌈Σ i ==1 n (1/ w i ) be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used H + O (ln H ) channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most H + 1 bins. In the online setting, this article presents algorithms for both problems with H + O (√ H ) channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least H +Ω(ln H ) bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.

This paper studies deterministic algorithms for a frequency assignment problem in cellular networks. A cellular network consists of fixed-position base stations and moving agents. Each base station operates at a fixed frequency, and this allows an agent tuned at this frequency to communicate with the base station. Each agent has a specific range of communication (described as a geometric shape, e.g., a disc) that may contain one or several base stations. To avoid interference, the goal is to assign frequencies to base stations such that for any range, there exists a base station in the range with a frequency that is not reused by some other base station in the range. The base station with this unique (in the range) frequency serves the aforementioned range. Since using many frequencies is expensive, the optimization goal is to use as few frequencies as possible. The problem can be modeled as a special coloring problem for hypergraphs. Base stations are the vertices, ranges are the hyperedges, and colors (frequencies) must be assigned to vertices following the conflict-free property: In every hyperedge there is a color that occurs exactly once.We concentrate on the special case where the n base stations lie on the real line and ranges are the n(n+1)/2 nonempty subsets of consecutive points. This problem is called conflict-free coloring for intervals. We introduce a hierarchy of four models for the above problem: (i) the static model, where the complete hypergraph is given and all vertices are colored simultaneously, (ii) the dynamic offline model, where the vertices appear in some order and the conflict-free property has to be maintained at all times, (iii) the online absolute positions model where the order is revealed in an online fashion and the final hypergraph and positions are known, and (iv) the online relative positions model where there is no knowledge about the final hypergraph and the final positions of vertices.In the case of intervals, the hierarchy is strict. In the dynamic offline model, we give a deterministic algorithm that uses at most log3/2 n+1 colors and exhibit inputs that force any algorithm to use at least 2 log3 n + 1 colors. For the online absolute positions model, we give two deterministic algorithms that use at most 2⌊log2(n + 1)⌋ and 3⌈log3 n⌉ colors, respectively. To the best of our knowledge, these are the first O(log n) deterministic online algorithms, in a non-trivial model. In the online relative positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the natural greedy online algorithm, that at each step uses the smallest color possible. In the case of conflict-free coloring only with respect to intervals that contain either of the two extreme points, we show a strong separation between static and dynamic models and we provide tight bounds for all four models up to an additive term of two.

We consider live continuous broadcast (such as radio or TV) to which users can join with time-shifting. They can join the broadcast at time t and receive the broadcast of time t - w for some offset parameter w ges 0. The simplest implementation that supports such a feature allocates a dedicated channel for each arrival time t and offset value w. Using such a technique, the server bandwidth quickly becomes a bottleneck. We adapt the stream merging technique to the time-shifting model, which allows us to greatly reduce the required server bandwidth. In addition to the application of distributing popular media, there are many other applications such as distance learning and large Internet events that could benefit from the use of time-shifting

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I =\ang(w1, l1),(w2, l 2),...,(wn, ln) of n pairs of positive integers that are associated with the jobs 1,2,...,n, respectively. The processing length of job i is li slots (a slot is the processing time of one length unit). The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible parallel machines such that the gap (window) between two consecutive executions of the first slot of job i is at most wi slots. This problem arises in push broadcast systems in which data is transmitted on parallel channels.

The issue of tracking a group of users is discussed in this study. Given the condition that the search is over only after all the users in the group are found, this problem is called the conference call search (CCS) problem. The goal is to design efficient CCS strategies under delay and bandwidth constraints. While the problem of tracking a single user has been addressed by many studies, to the best of our knowledge, this study is one of the first attempts to reduce the search cost for multiple users. Moreover, as oppose to the single user tracking, for which one can always reduce the expected search delay by increasing the expected search cost, for a multiple users search the dependency between the delay and the search cost is more complicated, as demonstrated in this study. We identify the key factors affecting the search efficiency, and the dependency between them and the search delay. Our analysis shows that under tight bandwidth constraints, the CCS problem is NP-hard. We therefore propose a search method that is not optimal, but has a low computational complexity. In addition, the proposed strategy yields a low search delay as well as a low search cost. The performance of the proposed search strategy is superior to the implementation of an optimal single user search on a group of users.

A mobile user is roaming in a zone of n cells in a cellular network system. When a call for the mobile arrives, the system pages the mobile in these cells since it never reports its location unless it leaves the zone. A delay constraint paging strategy must find the mobile after at most 1 ≤ D ≤ n paging rounds each pages a subset of the n cells. The goal is to minimize the number of paged cells until the mobile is found. Optimal solutions are known for the off-line case, for which an a priori probability of a mobile residing in any one of the cells is known. In this paper we address the on-line case. An on-line paging strategy makes its decisions based only on past locations of the mobile while trying to learn its future locations.We present deterministic and randomized on-line algorithms for various values of D (number of paging rounds) as a function of n (number of cells) and evaluate them using competitive analysis. In particular, we present a constant competitive on-line algorithm for the two extreme cases of D=2 and D=n. The former is the first nontrivial delay constraint case and the latter is the case for which there are no delay constraints. We then show that the constant competitiveness can be attained already for D ≥ log2n. All of the above algorithms are deterministic. Our randomized on-line algorithm achieves a near optimal performance for all values of D. This algorithm is based on solutions to the best expert problem.

We address the problem of designing optimal off-line algorithms that minimize the required bandwidth for media-on-demand systems that use stream merging. We concentrate on the case where clients can receive two media streams simultaneously and can buffer up to half of a full stream. We construct an O(nm) optimal algorithm for n arbitrary time arrivals of clients, where m is the average number of arrivals in an interval of a stream length. We then show how to adopt our algorithm to be optimal even if clients have a limited size buffer. The complexity remains the same. We also prove that using stream merging may reduce the required bandwidth by a factor of order $\rho L/\log(\rho L)$ compared to the simple batching solution where L is the length of a stream and $\rho\le 1$ is the density in time of all the n arrivals. On the other hand, we show that the bandwidth required when clients can receive an unbounded number of streams simultaneously is always at least 1/2 the bandwidth required when clients are limited to receiving at most two streams.

We address the problem of designing efficient solutions for media-on-demand in systems that use stream merging. In a stream merging system, the receiving bandwidth of clients is larger than the playback bandwidth and clients can buffer parts of the transmission to be played back later. Intelligent use of these resources allows bandwidth usage to be reduced exponentially over traditional unicast delivery of popular media. We design an off-line algorithm that, in O(n) time, computes an optimal off-line stream merging solution for the case when the time horizon n is known ahead of time. In addition, we describe an on-line delay guaranteed solution that operates without knowledge of the time horizon size, and show that it performs asymptotically close to the optimal off-line algorithm. The on-line algorithm is simpler to implement than previously proposed on-line stream merging algorithms, and empirically performs well when the intensity of client arrivals is high.

The windows scheduling problem is defined by the positive integers n, h, and w 1 , ...,w n . There are n pages where the windoww i is associated with pagei , and h is the number of slotted channels available for broadcasting the pages. A schedule that solves the problem assigns pages to slots such that the gap between any two consecutive appearances of page i is at most w i slots. We investigate two optimization problems. (i) The optimal windows scheduling problem: given w 1 , ..., w n find a schedule in which h is minimized. (ii) The optimal harmonic windows scheduling problem: given h find a schedule for the windows w i = i in which n is maximized. The former is a formulation of the problem of minimizing the bandwidth in push systems that support guaranteed delay, and the latter is a formulation of the problem of minimizing the startup delay in media-on-demand systems. For the optimal windows scheduling problem we present an algorithm that constructs asymptotically close to optimal schedules, and for the optimal harmonic windows scheduling problem we show how to achieve the largest known n's for all values of h.

In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design algorithm is a frequency request for each client, and its task is to construct a perfectly periodic schedule that matches the requests as "closely" as possible. The quality of the schedule is measured by the ratios between the requested frequency and the allocated frequency for each client (either by the weighted average or by the maximum of these ratios over all clients). Periodic schedules enjoy maximal fairness, and are very useful in many contexts of asymmetric communication, e.g., push systems and Bluetooth networks. However, finding an optimal periodic schedule is NP-hard in general. Tree scheduling is a methodology for developing perfectly periodic schedules with quality guarantees by constructing trees that correspond to periodic schedules. We explore a few aspects of tree scheduling. First, noting that a complete schedule table may be exponential in size, and that using the tree for scheduling directly may require logarithmic time on average, we give algorithms that find the next client to schedule in constant amortized time, using only polynomial space in most practical cases. Second, we present a few heuristic algorithms for generating schedules, based on analysis of optimal tree-scheduling algorithms, for both the average and maximum measures. Simulation results indicate that some of these heuristics produce excellent schedules in practice, sometimes even beating the best known non-periodic schedules.

A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore when the system is to establish a call between users it may need to search, or page, all the cells that it suspects the users are located in, to find the cells where the users currently reside. The search consumes expensive wireless links and so it is desirable to develop search techniques that page as few cells as possible.We consider cellular systems with c cells and m mobile users roaming among the cells. The location of the users is uncertain as given by probability distribution vectors. Whenever the system needs to find specific users, it conducts a search operation lasting some number of rounds (the delay constraint). In each round the system may check an arbitrary subset of cells to see which users are located there. In this setting the problem of finding one user with minimum expected number of cells searched is known to be solved optimally in polynomial time.In this paper we address the problem of finding several users with the same optimization goal. This task is motivated by the problem of establishing a conference call between mobile users. We first show that the problem is NP-hard. Then we prove that a natural and simple heuristic is a e/e-1 approximation solution.

We consider the problem of scheduling a set of jobs on a single shared resource using time-multiplexing. A perfectly-periodic schedule is one where resource time is divided into equal size “time-slots” quanta, and each job gets a time slot precisely every fixed interval of time (the period of the job). Periodic schedules are advantageous in distributed settings with synchronized clocks, since they require very little communication to establish, and thereafter no additional communication overhead is needed.

We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema.

In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to find a competitive assignment in which the maximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted (as opposed to weighted) problem all jobs have unit weight. In the fractional (as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary (as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. For the integral model with temporary jobs we show an algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case (both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e and e+1, respectively. We also show an $\Omega(\sqrt{n})$ lower bound when temporary jobs are allowed.

We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to find a nonpreemptive schedule that maximizes the weight of jobs that meet their respective deadlines. We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated) and the weight of the jobs (identical vs. arbitrary). All these variants are known to be NP-hard, and the two variants involving unrelated machines are also MAX-SNP hard. The specific results obtained are as follows: For identical job weights and unrelated machines: a greedy 2-approximation algorithm. For identical job weights and k identical machines: the same greedy algorithm achieves a tight $\frac{(1+1/k)^k}{(1+1/k)^k-1}$ approximation factor. For arbitrary job weights and a single machine: an LP formulation achieves a 2-approximation for polynomially bounded integral input and a 3-approximation for arbitrary input. For unrelated machines, the factors are 3 and 4, respectively. For arbitrary job weights and k identical machines: the LP-based algorithm applied repeatedly achieves a $\frac{(1+1/k)^k}{(1+1/k)^k-1}$ approximation factor for polynomially bounded integral input and a $\frac{(1+1/2k)^k}{(1+1/2k)^k-1}$ approximation factor for arbitrary input. For arbitrary job weights and unrelated machines: a combinatorial $(3+2\sqrt{2} \approx 5.828)$-approximation algorithm.

In broadcast disk systems, information is broadcast in a shared medium. When a client needs an item from the disk, it waits until that item is broadcast. The fundamental algorithmic problem for such systems is to determine the broadcast schedule based on the demand probability of items, and the cost incurred to the system by clients waiting. The goal is to minimize the mean access cost of a random client. Typically, it was assumed that the access cost is proportional to the waiting time. In this paper, we ask what are the best broadcast schedules for access costs which are arbitrary polynomials in the waiting time. These may serve as reasonable representations of reality in many cases, where the "patience" of a client is not necessarily proportional to its waiting time. We present an asymptotically optimal algorithm for a fluid model, where the bandwidth may be divided to allow for fractional concurrent broadcasting. This algorithm, besides being justified in its own right, also serves as a lower bound against which we test known discrete algorithms. We show that the Greedy algorithm has the best performance in most cases. Then we show that the performance of other algorithms deteriorate exponentially with the degree of the cost polynomial and approach the fractional solution for sub-linear cost. Finally, we study the quality of approximating the greedy schedule by a finite schedule.

In a satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files are provided by different providers and are accessed by many clients. The providers are independent and therefore files may share information. The clients who access these files may have different patterns of access. Some clients may wish to access more than one file at a time in any order, some clients may access one file out of of several files, and some clients may wish to access a second file only after accessing another file. The goal of the server is to order the files in a way that minimizes the access time of the clients given some a-priori knowledge of their access patterns. This paper introduces a clients-providers-servers model that represents certain environments better than the traditional clients-servers model. Then, we show that a random order of the data files performs well independent of the specific access pattern. Our main technical contribution is showing how to de-randomize the randomized algorithm that is based on selecting a random order. The resulting algorithm is a polynomial time deterministic algorithm that finds an order that achieves the bounds of the random order.

We present a general framework for solving resource allocation and scheduling problems.Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor.Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines; (ii) bandwidth allocation for sessions between two endpoints; (iii) general caching; (iv) dynamic storage allocation; (v) bandwidth allocation on optical line and ring topologies.For some of these problems we provide the first constant factor approximation algorithm.Our algorithms are simple and efficient.They use the local-ratio technique and can be equivalently interpreted within the primal-dual schema.

In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone model by a factor of $O(\frac{\log n}{\log\log k})$. No approximation algorithms were known for the general model considered in this paper.

We study the problem of scheduling files over a broadcast channel in an asymmetric environment. The goal is to minimize the mean response time for clients who access the broadcast channel. Asymmetric channels gained a lot of attention since they are used to model wireless communication, Teletext systems, and Web caching in satellite systems. This paper addresses the 2-files case. We design a simple algorithm that defines the optimal schedule given the demand probability for each file. The solution is extended to include two other important factors: dependencies between files and variable-length files. Adding dependencies is important in particular in the Web caching environment since clients may wish to access more than one file in the broadcast channel. For these extensions, we prove the surprising result that there exists a simple optimal schedule. Such a schedule is composed of a repeated pattern of AA...AB where A is the more "popular" file and B is the less "popular" file.

We consider the following fundamental scheduling problem.The input to the problem consists of n jobs and k machines.Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines.The goal is to find a schedule that maximizes the weight ofjobs that meet their deadline.We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated), and the weight of the jobs (identical vs. arbitrary).All these variants are known to be NP-Hard, and we observe that the two variants involving unrelated machines are also MAX-SNP hard.To the best of our knowledge, these are the first approximation algorithms for such problems in the non-preemptive off-line setting.1 Introduction Wcconsiderthefollowing fundamentalschedulingprohlem.The input lo the problem consists of n jobs and k machines.Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines.The goal is to find a schedulethat maximizes the weight of the jobs that meet theirdead-*Part of this work was done while the first three authors visited IBM T.I.

Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule "more valuable" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that nonpreemptive strategies have at most inverse logarithmic competitiveness.

We consider the problem of broadcasting multiple messages from one processor to many processors in the k-port model for message-passing systems. In such systems, processors communicate in rounds, where in every round, each processor can send k messages to k processors and receive k messages from k processors In this paper, we first present a simple and practical algorithm based on variations of k complete k-ary trees. We then present an optimal algorithm up to an additive term of one for this problem for any number of processors, any number of messages, and any value for k.

We propose a realistic theoretical model for dynamic bandwidth allocation. Our model takes into account the two classical quality of service parameters: latency and utilization, together with a newly introduced parameter: number of bandwidth allocation changes, which are costly operations in today's networks. Our model assumes that sessions join the network with a certain delay requirement rather than a bandwidth requirement as assumed in previous models. In addition, the network has a certain utilization requirement. Given bounds on latency and utilization, we design online algorithms that minimize the number of bandwidth allocation changes. 1 Introduction The phenomenal proliferation of communication networks during the recent years is due to both growth in the number of users and inflation in their bandwidth demand. Although the available bandwidth is increasing dramatically, it is still one of the bottleneck resources in communication networks. Sharing this resource efficiently is ...

In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages.The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit.We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the processors of size k.The problem is NP-hard even in the basic Telephone model.We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k).Our algorithm improves on the best known approximation factor for the Telephone model by a factor of 0 (e).No approximation algorithms were known for the general model considered in this paper. IntroductionThe task of disseminating a message from a source node to the rest of the nodes in a communication network is called bruudcczsting.The goal is to completethetask as fast as possible assuming all nodes in the network participate in the effort.When the message needs to be disseminated only to a subset of the nodes this task is referred to as mulricarring.Broadcasting and multicasting are important and basic communication primitives in many multiprocessor systems.Current networks usually provide point-to-point communication only between some of the pairs of the nodes in the network.Yet,

We introduce a new scheduling problem that is motivated by applications in the area of access and flow control in high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled "as often as possible." There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. These conflicts are presented in the form of a conflict graph. We define parameters which quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters and present fair and efficient scheduling algorithms for the case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.

Broadcasting is an important operation in many message-passing systems that has been widely investigated. Most existing broadcasting algorithms, however, do not address several emerging trends in distributed-memory parallel computers and high-speed communication networks. These trends include (i) treating the system as being fully connected with all processors equally distant, (ii) packetizing large amounts of data into sequences of messages, and (iii) tolerating communication latencies. In this paper, we explore the broadcasting problem in the postal model that addresses these issues. We provide two efficient algorithms for broadcasting m messages in a fully connected message-passing system with n processors and communication latency λ. A lower bound on the time required for this problem is (m - 1) + fλ(n), where fλ(n) is the optimal time for broadcasting one message. We present two algorithms: The first is Algorithm PARTITION, the running time of which is at most m + n + 2λ when m ≥ n and 3m + fλ(n) + 2λ when m ≤ n. The second is Algorithm D-D-TREES, the running time of which is at most m + 2fλ(n) + O(λ) for any value of m. © 1997 John Wiley & Sons, Inc.

This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical wavelength. A connection between two nodes is assigned a specific wavelength, with the constraint that no two connections sharing a link in the network can be assigned the same wavelength. This paper considers optical networks with and without switches, and different types of routing in these networks. It presents optimal or near-optimal constructions of optical networks in these cases and algorithms for routing connections, specifically permutation routing for the networks constructed here.

Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule "more valuable" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that non-preemptive strategies have at most inverse logarithmic competitiveness. An extended summary of this work appears in the proceedings ...

Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures. These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed systems. Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected. The overhead introduced by these emulations is polynomial in the number of processors in the system. Immediate new results are obtained by applying the emulators to known shared-memory algorithms. These include, among others, protocols to solve the following problems in the message-passing model in the presence of processor or link failures: multi-writer multi-reader registers, concurrent time-stamp systems,l-exclusion, atomic snapshots, randomized consensus, and implementation of data structures.

Consider a message-passing system of n processors, in which each processor holds one piece of data initially. The goal is to compute an associative and commutative reduction function on the n pieces of data and to make the result known to all the n processors. This operation is frequently used in many message-passing systems and is typically referred to as global combine, census computation, or gossiping. This paper explores the problem of global combine in the multiport postal model. This model is characterized by three parameters: n-the number of processors, k-the number of ports per processor, and /spl lambda/-the communication latency. In this model, in every round r, each processor can send k distinct messages to k other processors, and it can receive k messages that were sent from k other processors /spl lambda/-1 rounds earlier. This paper provides an optimal algorithm for the global combine problem that requires the least number of communication rounds and minimizes the time spent by any processor in sending and receiving messages.>

Tracking strategies for mobile users in wireless networks are studied. In order to save the cost of using the wireless links mobile users should not update their location whenever they cross boundaries of adjacent cells. The paper focuses on three natural strategies in which the mobile users make the decisions when and where to update: the time-based strategy, the number of movements-based strategy, and the distance-based strategy. The authors consider both memoryless movement patterns and movements with Markovian memory along a topology of cells arranged as a ring. They analyze the performance of each one of the three strategies under such movements, and show the performance differences between the strategies.>

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. We propose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (>

Tracking strategies for mobile wireless networks are studied, assuming a cellular architecture where base stations interconnected by a wired network communicate with mobile units via wireless links. The cost of utilizing the wireless links for the actual tracking of mobile users is investigated. A tracking strategy in which a subset of all base stations is selected and designated as reporting centers is proposed. Mobile users transmit update messages only upon entering cells of reporting centers, while every search for a mobile user is restricted to the vicinity of the reporting center to which the user last reported. It is shown that for an arbitrary topology of the cellular network (represented by the interference graph), finding an optimal set of reporting centers is an NP-complete problem. Optimal and near-optimal solutions for important special cases of the interference graph are given.>

We consider deflection routing on the n x n mesh

Tracking strategies for mobile wireless networks are studied. A cellular architecture in which base stations that are interconnected by a wired network communicate with mobile units via wireless links is assumed. The cost of utilizing the wireless links for the actual tracking of mobile users is considered. A tracking strategy in which a subset of all base stations is selected and designed as reporting centers is proposed. Mobile users transmit update messages only upon entering cells of reporting centers, while every search for a mobile user is restricted to the vicinity of the reporting center to which the user last reported. It is shown that, for an arbitrary topology of the cellular network (represented by the mobility graph), finding an optimal set of reporting centers is an NP-complete problem. Optimal and near-optimal solutions for important special cases of the mobility graph are presented.>

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red * Blue), where mod Red mod = n, mod Blue mod = m, n>

Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used in the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over an algorithm given by D.Z. Du et al. (1991), for which the competitive ratio was 2.75. It also proves a conjecture made by them. A new application of group testing techniques for high-speed networks is discussed.>

In many distributed-memory parallel computers and high-speed communication networks, the exact structure of the underlying communication network may be ignored. These systems assume that the network creates a complete communication graph between the processors, in which passing messages is associated with communication latencies. In this paper, we explore the impact of communication latencies on the design of broadcasting algorithms for fully-connected message-passing systems. For this purpose, we introduce the postal model that incorporates a communication latency parameter 1. This parameter measures the inverse of the ratio between the time it takes an originator of a message to send the message and the time that passes until the recipient of the message receives it. We present an optimal algorithm for broadcasting one message in systems with n processors and communication latency , the running time of which is \\Theta( log n log(+1) ). For broadcasting m 1 messages, we first e...

The set maxima problem is as follows: given a family of subsets $\mathcal{S}$ of a totally ordered set $X = \{ x_1 , \cdots ,x_n \}$, find the maximum in each subset. The computational model is the comparison tree. One possible solution is to sort the set X, which requires $O( n \log n )$ comparisons. The open question is whether set maxima is easier than sorting. Here, a solution is presented that requires a linear number of comparisons for the following two cases: • The sets are hyperplanes in a d-dimensional projective geometry $PG ( d,q )$. In particular, the interesting case is $PG ( 2,q )$, when the intersection of any two subsets is exactly one. • The sets are chosen randomly with probability $p ( n )$ for each element to be in a set. The random choices are mutually independent and the number of comparisons needed is linear with probability approaching 1 asymptotically.

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. Two modifications to the algorithm are proposed which result in polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (>

Mesh-connected computers with multiple buses providing broadcast facilities along rows and columns are discussed. A tight bound of Theta (n/sup 1/8/) is established for the number of rounds required for semigroup computations on n values distributed on a two-dimensional rectangular mesh of size n with a bus on every row and column. The upper bound is obtained for a skewed rectangular mesh of dimensions n/sup 3/8/*n/sup 5/8/. This result is compared to the tight bound of Theta (n/sup 1/6/) for the same problem on the square (n/sup 1/2/*n/sup 1/2/) mesh. It is shown that in the presence of multiple buses, a skewed configuration may perform better than a square configuration for certain computational tasks. The result can be extended to the d-dimensional mesh, giving a lower bound of Omega (n/sup 1/d alpha /) and an upper bound of O(d2/sup d+1/ n/sup 1/d alpha /), where alpha =2/sup d/; these bounds are optimal within constant factors for any constant d. It is noted that for d>3, the results of are mostly of theoretical interest.>

Emulators that translate algorithms from the sharedmemory model to two different message-passing models are presented.Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks.The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures.These results make it possible to view the sharedmemory model as a higher-level language for designing algorithms in asynchronous distributed systems.Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems.The overhead introduced by these emulations is polynomial in the number of processors in the systems.Immediate new results are obtained by applying the emulators to known shared-memory algorithms.

Routing a message in a network is efficient (in terms of weight of the path used to carry the message) when nodes know the full topology of the network. This may not be the case in large networks since a network may be composed of smaller autonomous pieces by design or by requirements on performance, with each piece having less than complete information about other pieces. We present a trade-off between the amount of topology information exchanged among these pieces and the efficiency of routing in the network. The large network that we study is a collection of networks connected by boundary nodes. Each boundary node knows the topology of its network and the connectivity of networks to each other. The question addressed here is how much topology information about each network should be distributed to other networks in order to achieve reasonably efficient routing.

This paper is concerned with the solvability of the problem of processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove in [8] that “nontrivial consensus” cannot be attained in such systems, even when only a single, benign processor failure is possible. In contrast, this paper shows that problems of processor renaming can be solved even in the presence of up tot

A general method is presented for translating sorting by comparisons algorithms to algorithms that compute a Hamilton path in a tournament. The translation is based on the relation between minimal feedback sets and Hamilton paths in tournaments. It is proven that there is a one to one correspondence between the set of minimal feedback sets and the set of Hamilton paths. In the comparison model, all the tradeoffs for sorting between the number of processors and the number of rounds hold as well for computing Hamilton paths. For the CRCW model, with $O( n )$ processors, we show the following: (i) Two paths in a tournament can be merged in $O(\log \log n)$ time (Valiant’s algorithm [SIAM J. Comput., 4 (1975), pp. 348–355], (ii) a Hamilton path can be computed in $O(\log n)$ time (Cole’s algorithm). This improves a previous algorithm for computing a Hamilton path whose running time was $O(\log^2 n)$ using $O(n^2 )$ processors.

No abstract available.

In this paper we consider mesh connected computers with multiple buses, providing broadcast facilities along rows and columns.A tight bound of O(n~) is established for the number of rounds required for semigroup computations on n values distributed on a 2-dimensional rectangular mesh of size n with a bus on every row and column.The upper bound is obtained for a skewed rectangular mesh of dinaensions n 3Is × n "5Is.This result is to be contrasted with the tight bound of @(n~) for the same problem on the square (n ~/2 x n ~/~') mesh [PR].This implies that in the presence of multiple buses, a skewed configuration may perform better than a square configuration for certain computationM tasks.Our result can be extended to the d-dimensional mesh, giving a lower bound of • 1 f 2 ( n ~' ) and an upper bound of O ( d 2 d + l n ~' ) .

A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. This paper is concerned with lower and upper bounds for the complexity of realizing various communication primitives for radio networks.

In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor - the maximum ratio between the cost of a route computed by the scheme and that of a cheapest path connecting the same pair of vertices.

Universal sequences for graphs, a concept introduced by Aleliunas [M.Sc. thesis, University of Toronto, Toronto, Ontario, Canada, January 1978] and Aleliunas et al. [Proc. 20th Annual Symposium on Foundation of Computer Science, 1979, pp. 218–223] are studied. By letting $U(d,n)$ denote the minimum length of a universal sequence for d-regular undirected graphs with n nodes, the latter paper has proved the upper bound $U(d,n) = O(d^2 n^3 \log n)$ using a probabilistic argument. Here a lower bound of $U(2,n) = \Omega (n\log n)$ is proved from which $U(d,n) = \Omega (n\log n)$ for all d is deduced. Also, for complete graphs $U(n - 1,n) = \Omega ({{n\log ^2 n} / {\log \log n}})$. An explicit construction of universal sequences for cycles $(d = 2)$ of length $n^{O(\log n)} $ is given.

A brief overview is given of current state of the art in robust multiagent decision making in a faulty environment (distributed consensus); and also a family of novel algorithms is presented to achieve consensus that are deterministic, simple, require single-bit messages, and can be implemented in hardware. For such systems to work properly, the issues of reaching common decision (consensus) in the presence of faults have to be addressed. The authors offer a structural solution to this problem. The approach is illustrated on a hypothetical example of a number of autonomous robots in manufacturing that all have to agree on a common decision determined by the values of some central controllers.>

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors.In this paper, we assume that messages consist of only one bit.Our main goal is to explore how the onebit translation of unbounded message algorithms can be sped up by pipelining.We consider three problems.The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube).The second problem is coloring a synchronous ring with three colors, and the third is counting the number of processors in a synchronous network where each processor knows only its neighbors.The routing problem is a very basic subroutine in many distributed al-

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that in such a system "nontrivial agreement" cannot be achieved even in the (possible) presence of a single "benign" fault. In contrast, we exhibit two pairs of goals that are achievable even in the presence of up to t ≪ n/2 faulty processors, contradicting the widely held assumption that no nontrivial goals are attainable in such a system. The first pair deals with renaming processors so as to reduce the size of the initial name space. When only uniqueness is required of the new names, we present a lower bound of n + 1 on the size of the new name space, and a renaming algorithm which establishes an upper bound of n + t. In case the new names are required also to preserve the original order, a tight bound of 2t(n- t + 1) - 1 is obtained. The second pair of goals deals with the multi-slot critical section problem. We present algorithms for controlled access to a critical section. As for the number of slots required, a tight bound of t + 1 is proved in case the slots are identical. In the case of distinct slots the upper bound is 2t + 1.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.

No abstract available.