35742857
Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks
We consider centralized deterministic broadcasting in radio networks. The aim is to design a polynomial algorithm, which, given a graph G, produces a fast broadcasting scheme in the radio network represented by G. The problem of finding an optimal broadcasting scheme for a given graph is NP-hard, hence we can only hope for a good approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcasting scheme working in time \({\cal O}(D \log n + \log ^2 n)\), for every n-node graph of diameter D. It has been proved recently [15,16] that a better order of magnitude of broadcasting time is impossible unless \(NP \subseteq BPTIME(n^{{\cal O}(\log \log n)})\). In terms of approximation ratio, we have a \({\cal O}(\log (n/D))\)-approximation algorithm for the radio broadcast problem, whenever D=Ω (log n).
34744258
Minimizing Congestion of Layouts for ATM Networks with Faulty Links
We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network Kn of n processors in which a certain number of links may fail. Our main goal is to construct layouts which tolerate any configuration of up to f faults and have the least possible congestion. First, we study the minimal congestion of 1-hop f-tolerant layouts in Kn. For any positive integer f we give upper and lower bounds on this minimal congestion and construct f-tolerant layouts with congestion corresponding to the upper bounds. Our results are based on a precise analysis of the diameter of the network Kn[ℱ] which results from Kn by deleting links from a set ℱ of bounded size. Next we study the minimal congestion of h-hop f-tolerant layouts in Kn, for larger values of the number h of hops. We give upper and lower bounds on the order of magnitude of this congestion, based on results for 1-hop layouts. Finally, we consider a random, rather than worst case, fault distribution where links fail independently with constant probability p<1. Our goal now is to construct layouts with low congestion that tolerate the existing faults with high probability. For any p<1, we show the existence of 1-hop layouts in Kn, with congestion O(log n).
6668725
Optimal Adaptive Fault Diagnosis for Simple Multiprocessor Systems
We study adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers give always correct test results, while faulty testers are completely unreliable. The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees, rings and tori. These algorithms use the smallest possible number of tests in each case. Our results also imply optimal diagnosis for more general systems, assuming a small number of faults. The cost of adaptive diagnosis turns out to be signiicantly smaller than that of classical (one-step) diagnosis.
16912745
Deterministic broadcasting in unknown radio networks
We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes are completely ignorant of the network: they know neither its topology, nor size, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. We study the time of deterministic broadcasting under this total ignorance scenario. Previous research has concentrated on distributed randomized broadcasting algorithms working for unknown networks, and on deterministic off-line broadcasting algorithms assuming full knowledge of the radio network. Ours are the first broadcasting algorithms simultaneously distributed and deterministic, that work for arbitrary totally unknown radio networks. The results for the model without collision detection: We develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal. For arbitrary n-node graphs, we prove a lower bound O(D log n), where D is the diameter, and develop an algorithm working in time 0(n11/~). Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs.
205093368
Weakly Adaptive Comparison Searching
We consider schemes of discrete search in the set {1,…,n} using only comparison queries, i.e. those of the form x<a? for aϵ{1,…,n}. Such a scheme is called i-adaptive if questions may be stated in i series, so that answers are obtained after each series but not between particular questions in it. We describe a worst-case optimal algorithm of i-adaptive search and determine its complexity. The latter turns out to be i·n1i where i may be a function of n. We also consider the closely related version of continuous search with a given error bound.
7003971
Prime decompositions of regular prefix codes
One of the new approaches to data classification uses finite state automata for representation of prefix codes. An important task driven by the need for the efficient storage of such automata in memory is the decomposition of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A linear time algorithm is designed which finds the prime decomposition <i>F</i><inf>1</inf><i>F</i><inf>2</inf>... <i>F<inf>k</inf></i> of a regular prefix code <i>F</i> given by its minimal deterministic automaton.
4612128
Gathering Asynchronous Oblivious Mobile Robots in a Ring
We consider the problem of gathering identical, memoryless, mobile robots in one node of an anonymous unoriented ring. Robots start from different nodes of the ring. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, a robot takes a snapshot of the current configuration (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. For an odd number of robots we prove that gathering is feasible if and only if the initial configuration is not periodic, and we provide a gathering algorithm for any such configuration. For an even number of robots we decide feasibility of gathering except for one type of symmetric initial configurations, and provide gathering algorithms for initial configurations proved to be gatherable.