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

We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the Min-Max Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of Min-Max Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-Traveling Salesmen Problem. In the Min-Max Tree Cover problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, Min-Max k-Rooted Tree Cover, the input also contains k roots r1, . . ., rk, and the ith tree must contain the root ri. These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an nO(k)-time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-Traveling Salesmen Problem, Min-Max Path Cover, and Min-Max Tree Cover on graphs of bounded treewidth.

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

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

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

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

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

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

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

Tor is one of the more popular systems for anonymizing near-real-time communications on the Internet. Borisov et al. [2007] proposed a denial-of-service-based attack on Tor (and related systems) that significantly increases the probability of compromising the anonymity provided. In this article, we analyze the effectiveness of the attack using both an analytic model and simulation. We also describe two algorithms for detecting such attacks, one deterministic and proved correct, the other probabilistic and verified in simulation.

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

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

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

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

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

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

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

In this paper, we present a reservation-based medium access control (MAC) protocol with multicast support for wavelength-division multiplexing networks. Our system is based on the single-hop, passive optical star architecture. Of the available wavelengths (channels), one channel is designated as a control channel, and the remaining channels are used for data transmission. Each node is equipped with a pair of fixed transceiver to access the control channel, and a fixed transmitter and a tunable receiver to access data channels. For easy implementation of the protocol in hardware and for precisely computing the protocol's processing overhead, we give a register-transfer model of the protocol. We simulate the protocol to study its throughput behavior, and present its analytic model. For a node to be able to send data packets in successive data slots with no time gap between them, in spite of the situation that the protocol's execution time may be longer than data transmission time, we propose the idea of multiple MAC units at each node. Unicast throughput of our protocol reaches the theoretically possible maximum throughput for MAC protocols with distributed control, and the multicast throughput is at least as good as, and even better than, those delivered by existing MAC protocols with distributed control.

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

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

We propose a reservation based multicast protocol for the single-hop passive optical star network. Of the available wavelengths (channels), one channel is designated as a control channel, and the remaining channels are used for data transmission. A node accesses the control channel using a fixed transmitter and a fixed receiver. A node sends data packets using a fixed transmitter and receives packets through a tunable receiver (filter). All the channels are viewed as sequences of frames. In addition, frames of the control channel are further divided into mini slots. Corresponding to each node in the network, there is a mini slot in a control frame. A node puts its multicast request in its designated mini slot in a control frame. At the end of a control frame, all nodes receive the multicast requests of all other nodes, and decide which nodes are going to transmit and/or receive during the following data slot. An easily implementable way of resolving destination and source conflicts is presented. We simulate the protocol to study its throughput behavior, and present its analytic model. Simulation results show that our protocol delivers maximum unicast throughput, and the protocol's multicast throughput is much better than existing protocols using a control channel.

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

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

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

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

No abstract available.

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

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

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

The existence of bounded degree networks which can emulate the computation of any bounded degree network of the same size with logarithmic slowdown is well-known. The butterfly is an example of such a universal network. Leiserson was the first to introduce the concept of an area-universal network: a network with VLSI layout area A which can emulate any network of the same size and layout area with logarithmic slowdown. His results imply the existence of an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(log N) slowdown. The main results of this paper are: There exists an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(loglogN) slowdown. The N-node butterfly (and hypercube) can emulate any network with VLSI layout area N/sup 2-/spl epsiv// (/spl epsiv/>0) with O(loglogN) slowdown. We also discuss sublogarithmic bounds for the slowdown of emulations of arbitrary bounded degree networks.>

In this paper, we present a new type of graph decomposition called a cut-cover that combines the notions of graph separators and t-neighborhood covers.We show that graphs with good cut-covers can be emulated in hypercubes and butterflies and we show that planar and certain minor-excluded graphs have good cut-covers.In particular, we show how to emulate any N-node bounded degree planar network or any N-node bounded degree graph that excludes KIOgOOl ~as a minor with constant slowdown on hypercube networks.We also show how to emulate any N-node bounded degree planar network or any IV-node bounded degree graph that excludes Ko(l) as a minor with O(log* N) slowdown on butterfly networks.

We show that sorting an input of size N = nz can be performed by an n x n mesh-connected processor array in 2n + O(n) parallel communication steps and using constant-size queues, with high probability.This result is optimal to within a low order additive term, realizing the obvious diameter lower bound.The best previously known algorithm for this problem required 2.5n + o(n) steps.Our techniques can be applied to higher dimensional meshes as well as torus-connected networks, achieving significantly better bounds than the known results.computers.While its diameter is large in comparison to other well-studied networks (e.g., hypercube, butterfly, shuffle-exchange networks), the simplicity and regularity of its interconnection pattern make it ideal for VLSI implementation.Recent work by Dally [Da187] suggests that high diameter networks such as the mesh may provide a more efficient communication medium for VLSI-based parallel computers.Furthermore, a large number of efficient algorithms have been

Article Free Access Share on Simple path selection for optimal routing on processor arrays Authors: Christos Kaklamanis View Profile , Danny Krizanc View Profile , Satish Rao View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 23–30https://doi.org/10.1145/140901.140904Published:01 June 1992Publication History 13citation290DownloadsMetricsTotal Citations13Total Downloads290Last 12 Months12Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An optimal lower bound on the average time required by any algorithm that merges two sorted lists on Valiant’s parallel computation tree model is proven.

we show that sorting an input of size N = n2 can be performed by an n x n mesh-connected processor array in 2.5n + o(n) parallel communication steps and using constant size queues, with high probability.The best previously known algorithm for this problem required 37L + o(n) steps.We also show that selecting the element of rank k out of N = n2 inputs on an n x n mesh can be performed in 1.25n + o(n) steps and using constant size queues, with high probability.The best previously known algorithm for this problem involved sorting, and required 3n + o(n) steps.Both of our algorithms can be generalized to higher dimensions, achieving bounds better than the known results.

The problem of oblivious routing in fixed connection networks with a limited amount of space available to buffer packets is studied. We show that for an n processor network with a constant number of connections and a constant number of buffers any deterministic pure source-oblivious strategy realizing all partial permutations requires Ω(n) time. The consequence of this result for well-known networks is discussed.

Article Free Access Share on Tight bounds for oblivious routing in the hypercube Authors: C. Kaklamanis Aiken Computation Laboratory, Harvard University, Cambridge, MA Aiken Computation Laboratory, Harvard University, Cambridge, MAView Profile , D. Krizanc Department of Computer Science, University of Rochester, Rochester, NY Department of Computer Science, University of Rochester, Rochester, NYView Profile , T. Tsantilas Aiken Computation Laboratory, Harvard University, Cambridge, MA Aiken Computation Laboratory, Harvard University, Cambridge, MAView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 31–36https://doi.org/10.1145/97444.97453Published:01 May 1990Publication History 57citation682DownloadsMetricsTotal Citations57Total Downloads682Last 12 Months63Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Three parameters characterize the performance of a probabilistic algorithm: T, the runtime of the algorithm; Q, the probability that the algorithm fails to complete the computation in the first T steps and R, the amount of randomness used by the algorithm, measured by the entropy of its random source.We present a tight tradeoff between these three parameters for the problem of oblivious packet routing on N-vertex bounded-degree networks. We prove a (1 - Q) log N/T - log Q - O(1) lower bound for the entropy of a random source of any oblivious packet routing algorithm that routes an arbitrary permutation in T steps with probability 1 - Q. We show that this lower bound is almost optimal by proving the existence, for every e3 log N ≤ T ≤ N1/2, of an oblivious algorithm that terminates in T steps with probability 1 - Q and uses (1-Q+o(1))logN/T-logQ independent random bits.We complement this result with an explicit construction of a family of oblivious algorithms that use less than a factor of log N more random bits than the optimal algorithm achieving the same run-time.

We prove a worst case lower bound of Ω(log log n) for randomized algorithms merging two sorted lists of length n in parallel using n processors on Valiant's parallel computation tree model. We show how to strengthen this result to a lower bound for the expected time taken by any algorithm on the uniform distribution. Finally, bounds are given for the average time required for the problem when the number of processors is less than and greater than n.