In the distributed localisation problem (DLP), n anonymous robots (agents) A_0, ..., A_{n-1} are located at arbitrary points p_0, ..., p_{n-1} ∈ S, where S is a Euclidean space. Initially, each agent A_i operates within its own coordinate system in S, which may be inconsistent with those of other agents. The primary goal in DLP is for agents to reach a consensus on a unified (jointly agreed) coordinate system, in which all agents receive unique labels (coordinates) that accurately reflect the relative distances between all points p_0, ..., p_{n-1} in S. Extensive research on DLP has primarily focus on the feasibility and complexity of achieving consensus when agents have limited access to inter-agent distances, often due to missing or imprecise data. In contrast, this paper proposes a minimalist, computationally efficient distributed computing model where agents can query any pairwise relative positions, if needed. Specifically, we introduce a novel variant of population protocols, referred to as the spatial population protocols model. In this variant each agent can memorise one or a fixed number of coordinates, and when agents A_i and A_j interact, they can not only exchange their current knowledge but also either determine the distance d_{ij} between them in S (distance query model) or obtain the vector v_{ij} spanning points p_i and p_j (vector query model). We propose and analyse several distributed localisation protocols, including: 1) Leader-based localisation protocol with distance queries We propose and analyse two leader-based localisation protocols that stabilise silently in o(n) time. These protocols leverage an efficient solution to the novel concept of multi-contact epidemic, a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. 2) Self-stabilising leader localisation protocol with distance queries We show how to effectively utilise a leader election mechanism within the leader-based localisation protocol to get a DLP protocol that self-stabilises silently in time O(n(log n/n)^{1/(k+1)}log n) in k-dimensions. 3) Self-stabilising localisation protocol with vector queries We propose and analyse an optimally fast DLP protocol which self-stabilises silently in O(log n) time.

We study leader election problem via ranking within self-stabilising population protocols. In this scenario, the agent's state space comprises n rank states and x extra states. The initial configuration of n agents consists of arbitrary arrangements of rank and extra states, with the objective of self-ranking. Specifically, each agent is tasked with stabilising in a unique rank state silently, implying that after stabilisation, each agent remains in its designated state indefinitely.

We consider the fundamental problem of assigning distinct labels to agents in theprobabilistic model of population protocols. Our protocols operate under the assumptionthat the size n of the population is embedded in the transition function. W.h.p. (withhigh probability), they are silent, i.e., eventually each agent reaches its nal state andremains in it forever, and they are safe, i.e., never change a label that has already beenassigned to an agent. We provide efficient protocols for this problem complemented withtight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε > 0 and 0 < a < 1,while our nearly state-optimal protocol uses only n + 5√n + O(log logn) states, the labelrange [1,n], and w.h.p., O(n3) interactions.

Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks on a single machine subject to given maximal time spans (a.k.a. frequencies) between any two consecutive executions of the same task. The density of a Pinwheel Scheduling instance is the sum of the inverses of these task frequencies; the 5/6-Conjecture (Chan and Chin, 1993) states that any Pinwheel Scheduling instance with density at most 5/6 is schedulable. We formalize the notion of Pareto surfaces for Pinwheel Scheduling and exploit novel structural insights to engineer an efficient algorithm for computing them. This allows us to (1) confirm the 5/6-Conjecture for all Pinwheel Scheduling instances with at most 12 tasks and (2) to prove that a given list of only 23 schedules solves all schedulable Pinwheel Scheduling instances with at most 5 tasks.

In this paper we consider a known variant of the standard population protocol model in which agents can be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The state space of agents is fixed (constant size) and the size n of the population is not known, i.e., not hard-coded in the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(polylog n) parallel time. The main focus in this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model. - We propose and analyse a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guaranties in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n). - The new clock enables a nearly optimal O(nlog n) parallel time spanning line construction (a key component of universal network construction), which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016]. - We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are allowed only between the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting (via conditional pipelining) procedure requires O(n²) comparisons in expectation and whp, and is on par with its deterministic counterpart. - We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying a k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The pipelining mechanism and the time complexity analysis of the strand self-replication protocol mimic those used in the probabilistic bubble-sort. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in time O(n(k+log n)log l). Finally, we discuss application of the strand self-replication protocol to pattern matching. Our protocols are always correct and provide time guaranties with high probability defined as 1-n^{-η}, for a constant η > 0.

We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The majority problem is that of determining in an initial population of$n$agents, each with one of two opinions$A$or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol solving this problem using O(log n) states (log log$n$+ O(1) bits of memory) and optimal expected time$O$(log$n$). The number of states$O$(log$n$) is known to be optimal for polylogarithmic time stable protocols that are “output dominant” and “monotone” [1]. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. We introduce a key technique called a “fixed resolution clock” to achieve partial synchronization. Our protocol is nonuniform: the transition function has the value [log$n$] encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ (log$n$log log n).

We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size n of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1).

We study population protocols, a model of distributed computing where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied majority problem is that of determining in an initial population of n agents, each with one of two opinions A or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol that solves this problem using O(log n) states (log log n + O(1) bits of memory) and optimal expected time O(log n). The number of states O(log n) is known to be optimal for the class of polylogarithmic time stable protocols that are "output dominant'' and "monotone''. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. Our protocol is nonuniform : the transition function has the value log n encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ(log n log log n).

In the ad-hoc radio network model, nodes communicate with their neighbors via radio signals, without knowing the topology of the underlying digraph. We study the information gathering problem, where each node has a piece of information called a rumor, and the objective is to transmit all rumors to the designated target node. For the model without any collision detection we provide an O˜(n1.5) deterministic protocol, significantly improving the trivial bound of O(n2). We also consider a model with a mild form of collision detection, where a node receives a 1-bit acknowledgment if its transmission was received by at least one out-neighbor. For this model we give an O˜(n) deterministic protocol for information gathering in acyclic graphs.

The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents . In this article, the emphasis is on the space complexity of fast leader election in population protocols governed by the random scheduler , which uniformly at random selects pairwise interactions between n agents. One of the main results of this article is the first fast space optimal leader election protocol , which works with high probability. The new protocol operates in parallel time O (log 2 n ) equivalent to O ( n log 2 n ) sequential pairwise interactions with each agent’s memory space limited to O (log log n ) states. This double logarithmic space utilisation matches asymptotically the lower bound ½log log n on the number of states utilised by agents in any leader election algorithm with the running time o ( n \polylog n ); see Reference [7]. Our new solution expands also on the classical concept of phase clocks used to synchronise and to coordinate computations in distributed algorithms. In particular, we formalise the concept and provide a rigorous analysis of phase clocks operating in nested modes. Our arguments are also valid for phase clocks propelled by multiple leaders. The combination of the two results in the first time-space efficient leader election algorithm. We also provide a complete formal argumentation, indicating that our solution is always correct, fast, and it works with high probability.

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

The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called \em agents. The agents communicate and perform computation through pairwise interactions. We study fast and space efficient leader election in population of cardinality n governed by a random scheduler, where during each time step the scheduler uniformly at random selects for interaction exactly one pair of agents. We present the first $o(łog^2)$-time leader election protocol. It operates in expected parallel time $\bigo(łog nłogłog n)$ which is equivalent to $\bigo(n łog nłogłog n)$ pairwise interactions. This is the fastest currently known leader election algorithm in which each agent utilises asymptotically optimal number of $\bigo(łogłog n)$ states. The new protocol incorporates and amalgamates successfully the power of assorted \em synthetic coins with variable rate \em phase clocks.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most $$\sqrt{17}+4\approx 8.123$$ times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions from the population of n agents. The main result of this paper is a new fast and space optimal leader election protocol. The new protocol operates in parallel time O(log2 n) equivalent to O(n log2 n) sequential pairwise interactions, in which each agent utilises O(log log n) states. This double logarithmic space utilisation matches asymptotically the lower bound ½ log log n on the number of states utilised by agents in any leader election algorithm with the running time , see [7]. Our solution relies on the concept of phase clocks, a fundamental synchronisation and coordination tool in the field of Distributed Computing. We propose a new fast and robust population protocol for initialisation of phase clocks to be run simultaneously in multiple modes and intertwined with the leader election process. We also provide the reader with the relevant formal argumentation indicating that our solution is always correct and fast with high probability.

We study the problem of efficiently correcting an erroneous product of two $$n\times n$$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in $${\tilde{O}}(n^2+kn)$$ time and a deterministic $${\tilde{O}}(kn^2)$$ -time algorithm for this problem (where the notation $${\tilde{O}}$$ suppresses polylogarithmic terms in n and k).

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u, v, u ≠ v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = N P. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels.

In this paper we study space-efficient deterministic population protocols for several variants of the majority problem including plurality consensus. We focus on space efficient majority protocols in populations with an arbitrary number of colours C represented by k-bit labels, where k = ceiling (log C). In particular, we present asymptotically space-optimal (with respect to the adopted k-bit representation of colours) protocols for (1) the absolute majority problem, i.e., a protocol which decides whether a single colour dominates all other colours considered together, and (2) the relative majority problem, also known in the literature as plurality consensus, in which colours declare their volume superiority versus other individual colours. The new population protocols proposed in this paper rely on a dynamic formulation of the majority problem in which the colours originally present in the population can be changed by an external force during the communication process. The considered dynamic formulation is based on the concepts studied by D. Angluin et al. and O. Michail et al. about stabilizing inputs and composition of population protocols. Also, the protocols presented in this paper use a composition of some known protocols for static and dynamic majority.

Decentralized monitoring and alarming systems can be an attractive alternative to centralized architectures. Distributed sensor nodes (e.g., in the smart grid's distribution network) are closer to an observed event than a global and remote observer or controller. This improves the visibility and response time of the system. Moreover, in a distributed system, local problems may also be handled locally and without overloading the communication network. This paper studies alarming from a distributed computing perspective and for two fundamentally different scenarios: on-duty and off-duty. We model the alarming system as a sensor network consisting of a set of distributed nodes performing local measurements to sense events. In order to avoid false alarms, the sensor nodes cooperate and only escalate an event (i.e., raise an alarm) if the number of sensor nodes sensing an event exceeds a certain threshold. In the on-duty scenario, nodes not affected by the event can actively help in the communication process, while in the off-duty scenario, non-event nodes are inactive. We present and analyze algorithms that minimize the reaction time of the monitoring system while avoiding unnecessary message transmissions. We investigate time and message complexity tradeoffs in different settings, and also shed light on the optimality of our algorithms by deriving cost lower bounds for distributed alarming systems.

We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronised rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., When an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem.

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum time (lifetime of the net). More specifically, our temporal networks notion concerns networks, whose edges (arcs) are assigned one or more random discrete-time labels drawn from a set of natural numbers. The labels of an edge indicate the discrete moments in time at which the edge is available. In such networks, information (e.g., messages) have to follow temporal paths, i.e., paths, the edges of which are assigned a strictly increasing sequence of labels. We first examine a very hostile network: a clique, each edge of which is known to be available only one random time in the time period {1,2, ..., n} (n is the number of vertices). How fast can a vertex send a message to all other vertices in such a network? To answer this, we define the notion of the Temporal Diameter for the random temporal clique and prove that it is Θ(log n) with high probability and in expectation. In fact, we show that information dissemination is very fast with high probability even in this hostile network with regard to availability. This result is similar to the results for the random phone-call model. Our model, though, is weaker. Our availability assumptions are different and randomness is provided only by the input. We show here that the temporal diameter of the clique is crucially affected by the clique's lifetime, a, e.g., when a is asymptotically larger than the number of vertices, n, then the temporal diameter must be Ω(a/nlog n ). We, then, consider the least number, r, of random points in time at which an edge is available, in order to guarantee at least a temporal path between any pair of vertices of the network (notice that the clique is the only network for which just one instance of availability per edge, even non-random, suffices for this). We show that r is Ω(log n) even for some networks of diameter 2. Finally, we compare this cost to an (optimal) deterministic allocation of labels of availability that guarantees a temporal path between any pair of vertices. For this reason, we introduce the notion of the Price of Randomness and we show an upper bound for general networks.

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.

In the packed string matching problem, each machine word accomodates alpha characters, thus an n-character text occupies n/alpha memory words. We extend the Crochemore-Perrin constant-space O(n)-time string matching algorithm to run in optimal O(n/alpha) time and even in real-time, achieving a factor alpha speedup over traditional algorithms that examine each character individually. Our solution can be efficiently implemented, unlike prior theoretical packed string matching work. We adapt the standard RAM model and only use its AC0 instructions (i.e. no multiplication) plus two specialized AC0 packed string instructions. The main string-matching instruction is available in commodity processors (i.e. Intel's SSE4.2 and AVX Advanced String Operations); the other maximal-suffix instruction is only required during pattern preprocessing. In the absence of these two specialized instructions, we propose theoretically-efficient emulation using integer multiplication (not AC0) and table lookup.

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O (log n )-bit memory for all n -node trees. This strengthens the result from Diks et al. [2004], where O (log 2 n )-bit memory was used for tree exploration, and matches the lower bound on memory size proved there. We also extend our O (log n )-bit memory traversal mechanism to a weaker model in which ports at each node are ordered in circular manner, however, the explicit values of port numbers are not available.

We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round, every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availability of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible, and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(log2n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(log2n).

We study broadcasting (one-to-all communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on limited number of transmissions at each node.

We consider broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time.In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning.

We study the problem of waking up a collection of n processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up spontaneously or gets activated by receiving a wake‐up signal from another node. All active nodes transmit the wake‐up signals according to a given protocol $\calW$. The running time of $\calW$ is the number of steps counted from the first spontaneous wake‐up until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time $O(n^{5/3}\log n)$. Our protocol is based on a novel concept of a shift‐tolerant selector to which we refer as a (radio) synchronizer. The second protocol is randomized, and its expected running time is $O(D \log^2 n)$, where D is the diameter of the network. Subsequently we show how to employ our wake‐up protocols to solve two other communication primitives: leader election and clock synchronization.

The DNA microarray technology, originally developed to measure the level of gene expression, had become one of the most widely used tools in genomic study. Microarrays have been proved to benefit areas including gene discovery, disease diagnosis, and multi-virus discovery. The crux of microarray design lies in how to select a unique probe that distinguishes a given genomic sequence from other sequences. However, in cases that the existence of a unique probe is unlikely, e.g., in the context of a large family of closely homologous genes, the use of a limited number of non-unique probes is still desirable.qyy Due to its significance, probe selection attracts a lot of attention. Various probe selection algorithms have been developed in recent years. Good probe selection algorithms should produce as small number of candidate probes as possible. Efficiency is also crucial because the data involved is usually huge. Most existing algorithms usually select probes by filtering, which is usually not selective enough and quite a large number of probes are returned. We propose a new direction to tackle the problem and give an efficient algorithm to select (randomly) a small set of probes and demonstrate that such a small set of probes is sufficient to distinguish each sequence from all the other sequences. Based on the algorithm, we have developed a probe selection software RANDPS, which runs efficiently and effectively in practice. A number of experiments have been carried out and the results will be discussed.

Summary form only given. In text compression applications, it is important to be able to process compressed data without requiring (complete) decompression. In this context it is crucial to study compression methods that allow time/space efficient access to any fragment of a compressed file without being forced to perform complete decompression. We study here the real-time recovery of consecutive symbols from compressed files, in the context of grammar-based compression. In this setting, a compressed text is represented as a small (a few Kb) dictionary D (containing a set of code words), and a very long (a few Mb) string based on symbols drawn from the dictionary D. The space efficiency of this kind of compression is comparable with standard compression methods based on the Lempel-Ziv approach. We show, that one can visit consecutive symbols of the original text, moving from one symbol to another in constant time and extra O(|D|) space. This algorithm is an improvement of the on-line linear (amortised) time algorithm presented in (L. Gasieniec et al, Proc. 13th Int. Symp. on Fund. of Comp. Theo., LNCS, vol.2138, p.138-152, 2001).

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in radio networks with known topology, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network.The first part of the paper examines the two communication primitives in general graphs. In particular, it proposes a new (efficiently computable) deterministic schedule that uses O(D+Δ log n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time O(D+√[i+2]DΔ logi+1 n), for any network with the diameter D=Ω(logi+4n), where i is an arbitrary integer constant i ≥ 0, see [17]. For the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D+O(log3 n), and a randomized algorithm for computing a radio schedule of length D+O(log2 n). These results improve on the best currently known D+O(log4 n) time schedule due to Elkin and Kortsarz [12].The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on currently best known D+O(log3n) time schedule proposed by Elkin and Kortsarz in [12]. Our new algorithm should be also seen as the separation result between the planar and the general graphs with a small diameter due to the polylogarithmic inapproximability result in general graphs due to Elkin and Kortsarz, see [11].

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. We propose here several time efficient, centralized as well as fully distributed procedures for the broadcasting problem in random radio networks. In particular we show how to perform a centralized broadcast in a random graph Gp=(V,E) of size n=|V| and expected average degree d=pn in time O(ln n/lnd+lnd). Later we present a randomized distributed broadcasting algorithm with the running time O(ln n). In both cases we show that the presented algorithms are asymptotically optimal by deriving lower bounds on the complexity of radio broadcasting in random graphs. In these proofs we determine some structural properties in random graphs which may be of independent interest. We should note here that the results of this paper hold with probability 1-o(1/n).

Group testing refers to the situation in which one is given a set of objects ${\cal O}$, an unknown subset ${\cal P}\subseteq {\cal O}$, and the task of determining ${\cal P}$ by asking queries of the type "does ${\cal P}$ intersect $\cal Q$?," where $\cal Q$ is a subset of ${\cal O}$. Group testing is a basic search paradigm that occurs in a variety of situations such as quality control testing, searching in storage systems, multiple access communications, and data compression, among others. Group testing procedures have been recently applied in computational molecular biology, where they are used for screening libraries of clones with hybridization probes and sequencing by hybridization. Motivated by particular features of group testing algorithms used in biological screening, we study the efficiency of two-stage group testing procedures. Our main result is the first optimal two-stage algorithm that uses a number of tests of the same order as the information-theoretic lower bound on the problem. We also provide efficient algorithms for the case in which there is a Bernoulli probability distribution on the possible sets ${\cal P}$, and an optimal algorithm for the case in which the outcome of tests may be unreliable because of the presence of "inhibitory" items in ${\cal O}$. Our results depend on a combinatorial structure introduced in this paper. We believe that it will prove useful in other contexts, too.

Abstract We present an O ( n log 4 n )‐time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O ( n 3/2 log 2 n ). © 2004 Wiley Periodicals, Inc.

This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually when the processor wakes up. We consider the fundamental problem of waking up all n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models.

We establish an O(n log/sup 2/n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of /spl Omega/(n log n). The fastest previously known algorithm for this problem works in time O(n/sup 3/2/). Using our broadcasting algorithm, we develop an O(n/sup 3/2/log/sup 2/n) algorithm for gossiping in the same network model.

This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually, when the processor wakes up.

Given two strings: pattern P and text T of lengths |P|=M and |T|=N, a string matching problem is to find all occurrences of pattern P in text T. A fully compressed string matching problem is the string matching problem with input strings P and T given in compressed forms p and t respectively, where |p|=m and |t|=n. We present first, almost-optimal, string matching algorithms for LZW-compressed strings running in: (1) O((n+m)log(n+m)) time on a single processor machine; and (2) O/sup /spl tilde//(n+m) work on a (n+m)-processor PRAM. The techniques used can be used in design of efficient algorithms for a wide range of the most typical string problems, in the compressed LZW setting, including: computing a period of a word, finding repetitions, symmetries, counting subwords, and multi-pattern matching.

We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m h x m w in a text array of size n h x n w in the concurrent-read-concurrent-write--parallel-random-access-machine (CRCW--PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n h x n w ) work, following preprocessing of the pattern. This improves the previous best bound of O(log log m ) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 79--85], following preprocessing of the pattern, where m=max{m h , m w }. The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(log log m) time and O(m h x m w ) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

Each of n processors has a value which should be transmitted to all other processors. This fundamental communication task is called gossiping. In a unit of time every processor can communicate with at most one other processor and during such a transmission each member of a communicating pair learns all values currently known to the other. Two important criteria of efficiency of a gossiping algorithm are its running time and the total number of transmissions. Another measure of quality of a gossiping algorithm is the total number of links used for transmissions. This is the minimum cost of a network which can support the gossiping algorithm. We establish trade-offs between the time T of gossiping and the number C of transmissions and between the time of gossiping and the number L of links used by the algorithm. For a given T we construct gossiping algorithms working in time T, with parameters C and L close to optimal.

Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log 2 m / log log m). We use this algorithm to obtain the following results (all algorithms below are optimal parallel algorithms on a CRCW PRAM): a deterministic string-matching algorithm which takes O(log log m) time for preprocessing and constant time for text search, which are the best possible in both preprocessing and text search; a constant-time deterministic string-matching algorithm in the case where the text length n satisfies $n=\Omega(m^{1+\epsilon})$ for a constant $\epsilon > 0$; a simple string-matching algorithm that has constant time with high probability for random input; the main result: a constant-expected-time Las Vegas algorithm for computing the period of the pattern and all witnesses and thus for string matching itself; in both cases, an $\Omega(\log\log m)$ lower bound is known for deterministic algorithms.

A parallel algorithm is work-optimal if it uses the srrlallest possible work; a work-optimal algorithm is worktirne-optimal if it also uses the smallest possible time.We design worl{-time-optirnal algorithm for a number of string processing problems on the EREW-PRAM and the hypercuhe, They include string matching and two dimensional pattern matching.No such algorithms have been known before for any of these probl~ms.

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching.>