P. Fraigniaud, L. Gasieniec, D. Kowalski, A. Pelc,
Collective tree exploration,
Networks 48 (2006), 166-177.
P. Fraigniaud, L. Gasieniec, D. Kowalski, A. Pelc,
Collective tree exploration,
Networks 48 (2006), 166-177.
Preliminary version appeared in:
Proc. Latin American Theoretical Informatics (LATIN'2004), April 2004, Buenos Aires, Argentina, LNCS 2976, 141-151.
Abstract:
An n-node tree has to be explored by k mobile agents (robots), starting at its root. Every edge of the tree must be traversed by at least one robot, and exploration must be completed as fast as possible. Even when the tree is known in advance, scheduling optimal collective exploration turns out to be NP-hard. We investigate the problem of how communication among robots influences the time for exploring unknown trees. To this end, we consider two scenarios. In the first scenario, robots can communicate by writing at the currently visited node previously acquired information, and reading information available at this node. In the second scenario robots are oblivious of one another, and each of them knows only the part of the tree previously explored by itself. We show that this difference of communication capability significantly influences time of collective exploration. Under the first scenario, we construct an exploration algorithm whose running time for any tree is only O(k/\log k) larger than the optimal exploration time with full knowledge of the tree, while under the second scenario we prove that every algorithm works in time Omega (k) larger than optimal, for some trees.
G. De Marco, A. Pelc,
Randomized algorithms for determining the majority on graphs,
Combinatorics, Probability & Computing 15 (2006), 823-834.
Preliminary version appeared in:
Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003), August 2003, Bratislava, Slovakia, LNCS 2747, 368-377.
Abstract:
Every node of an undirected connected graph is colored white or black. Adjacent nodes can be compared and the outcome of each comparison is either 0 (same color) or 1 (different colors). The aim is to discover a node of the majority color, or to conclude that there is the same number of black and white nodes. We consider randomized algorithms for this task and establish upper and lower bounds on their expected running time. Our main contribution are lower bounds showing that some simple and natural algorithms for this problem cannot be improved in general.
L. Gasieniec, E. Kranakis, A. Pelc, Q. Xin,
Deterministic M2M multicast in radio networks,
Theoretical Computer Science 362 (2006), 196-206.
Preliminary version appeared in:
Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), July 2004, Turku, Finland, LNCS 3142, 670-682.
Abstract:
We study the problem of exchanging messages within a fixed group of k nodes, in an n-node multi-hop radio network, also known as the problem of Multipoint-to-Multipoint (M2M) multicasting. While the radio network topology is known to all nodes, we assume that the participating nodes are not aware of each other's positions. We give a new fully distributed deterministic algorithm for the M2M multicasting problem, and analyze its complexity. We show that if the maximum distance between any two out of k participants is d then this local information exchange problem can be solved in time O(dlog2 n+klog3 n). Hence our algorithm is linear in the size of the subnetwork induced by the participating nodes and only polylogarithmic in the size of the entire radio network.
K. Diks, S. Dobrev, A. Pelc,
Exploring planar graphs using unoriented maps,
Journal of Interconnection Networks 7 (2006), 353-373.
Preliminary version appeared in:
Proc. 15th Australasian Workshop on Combinatorial Algorithms (AWOCA'2004), July 2004, Ballina Beach Resort, New South Wales, Australia, 85-96.
Abstract:
A mobile agent (robot) has to explore an unknown terrain modeled as a planar embedding of an undirected planar connected graph. Exploration consists in visiting all nodes and traversing all edges of the graph, and should be completed using as few edge traversals as possible. The agent has an unlabeled map of the terrain which is another planar embedding of the same graph, preserving the clockwise order of neighbors at each node. The starting node of the agent is marked in the map but the map is unoriented: the agent does not know which direction in the map corresponds to which direction in the terrain. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, for a given input consisting of a graph and a starting node, is called the overhead of algorithm A for this input. We seek exploration algorithms with small overhead. We show an exploration algorithm with overhead of at most 7/5 for all trees, which is the best possible overhead for some trees. We also show an exploration algorithm with the best possible overhead, for any tree with starting node of degree 2. For a large class of planar graphs, called stars of graphs, we show an exploration algorithm with overhead of at most 3/2. Finally, we show a lower bound 5/3 on the overhead of exploration algorithms for some planar graphs.
A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc,
Deterministic rendezvous in graphs,
Algorithmica 46 (2006), 69-96.
Preliminary versions appeared as:
A. Dessmark, P. Fraigniaud, A. Pelc, Deterministic rendezvous in graphs, Proc. 11th Annual European Symposium on Algorithms (ESA'2003), September 2003, Budapest, Hungary, LNCS 2832, 184-195.
and as:
D. Kowalski, A. Pelc, Polynomial deterministic rendezvous in arbitrary graphs, Proc. 15th Annual Symposium on Algorithms and Computation (ISAAC'2004), December 2004, Hong Kong, LNCS 3341, 644-656.
Abstract:
Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Theta(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, tau and log l, where tau is the difference between startup times of the agents. We also show a lower bound Omega (n2) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.
G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro,
Asynchronous deterministic rendezvous in graphs,
Theoretical Computer Science 355 (2006), 315-326.
Preliminary version appeared in:
30th International Symposium on Mathematical Foundations of Computer Science, (MFCS 2005), August 2005, Gdansk, Poland, LNCS 3618, 271-282.
Abstract:
Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph, have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved.
A. Pelc,
Voting mechanisms in asynchronous Byzantine environments,
Parallel Processing Letters 16 (2006), 93-99.
Abstract:
A source sends a piece of data (message), relayed to a receiver by n processes, some of which can be faulty. We assume that the number of faulty processes is at most f and that faulty processes exhibit a Byzantine behavior. A deciding agent has to make a decision concerning the source message, on the basis of results obtained from the receiver. The environment is totally asynchronous. An Asynchronous Byzantine Voting Mechanism is a method that enables the deciding agent to always correctly determine the source message in this scenario.
We show that there exists a correct Asynchronous Byzantine Voting Mechanism if and only if f is less than n/3. If this condition is satisfied, we provide such a mechanism. This result should be contrasted with the feasibility of synchronous voting mechansisms, in which the receiver can wait until all fault-free processes convey their values: for this scenario a correct voting mechanism exists whenever f is less than n/2.
J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc,
Complexity of searching for a black hole,
Fundamenta Informaticae 71 (2006), 229-242.
Abstract:
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it.
T. Calamoneri, A. Pelc, R. Petreschi,
Labeling trees with a condition at distance two,
Discrete Mathematics 306 (2006), 1534-1539.
Preliminary version appeared in:
Proc. R.C. Bose Centenary Symposium on Discrete Mathematics and Applications, December 2002, Kolkata, India, Electronic Notes in Discrete Mathematics 15 (2003), 57-60.
Abstract:
An L(h,k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h,k)-labeling is the difference between the largest and the smallest label. We investigate L(h,k)-labelings of trees of maximum degree Delta, seeking those with small span. Given Delta, h and k, span lambda is optimal for the class of trees of maximum degree Delta, if lambda is the smallest integer such that every tree of maximum degree Delta has an L(h,k)-labeling with span at most lambda. For all parameters Delta,h,k, we construct L(h,k)-labelings with span either optimal or, in some cases, asymptotically optimal.
M. Paquette, A. Pelc,
Optimal decision strategies in Byzantine environments,
Journal of Parallel and Distributed Computing 66 (2006), 419-427.
Preliminary version appeared in:
Proc. 11th Colloquium on Structural Information and Communication Complexity (SIROCCO'2004), June 2004, Smolenice Castle, Slovakia, LNCS 3104, 245-254.
Abstract:
A Boolean value of given a priori probability distribution is transmitted to a deciding agent by several processes. Each process fails independently with given probability, and faulty processes behave in a Byzantine way. A deciding agent has to make a decision concerning the transmitted value on the basis of messages obtained by processes. We construct a deterministic decision strategy which has the provably highest probability of correctness. It computes the decision in time linear in the number of processes.
Decision optimality may be alternatively approached from a local, rather than global, point of view. Instead of maximizing the total probability of correctness of a decision strategy, we may try to find, for every set of values conveyed by processes, the conditionally most probable original value that could yield this set. We call such a strategy locally optimal, as it locally optimizes the probability of a decision, given a set of relayed values, disregarding the impact of such a choice on the overall probability of correctness. We construct a locally optimal decision strategy which again computes the decision value in time linear in the number of processes. We establish the surprising fact that, in general, local probability maximization may lead to a decision strategy which does not have the highest probability of correctness. However, if the probability distribution of the Boolean value to be conveyed is uniform, and all processes have the same failure probability smaller than 1/2, this anomaly does not occur.
We first design and analyze our strategies in the synchronous setting and then show how they should be modified to work in asynchronous systems.
M. Paquette, A. Pelc,
Fast broadcasting with Byzantine faults,
International Journal of Foundations of Computer Science 17 (2006), 1423-1439.
Preliminary version appeared in:
Proc. 7th IFAC Symposium on Cost Oriented Automation, June 2004, Gatineau-Ottawa, Canada, 311-316.
Abstract:
We construct and analyze a fast broadcasting algorithm working in the presence of Byzantine component faults. Such faults are particularly difficult to deal with, as faulty components may behave arbitrarily (even maliciously) as transmitters, by either blocking, rerouting, or altering transmitted messages in a way most detrimental to the broadcasting process. We assume that links and nodes of a communication network are subject to Byzantine failures, and that faults are distributed randomly and independently, with link failure probability p and node failure probability q, these parameters being constant and satisfying the inequality (1-p)2(1-q)>1/2. A broadcasting algorithm, working in an n-node network, is called almost safe if the probability of its correctness is at least 1-1/n, for sufficiently large n. Thus the robustness of the algorithm grows with the size of the network. Our main result is the design and analysis of an almost safe broadcasting algorithm working in time O(log 2 n) and using O(n log n) messages in n-node networks. Under a stronger assumption on failure probability parameters, namely (1-p)2(1-q)2>1/2, our algorithm can be modified to work in time O(log 2 n/log log n), also using O(n log n) messages. The novelty of our algorithm is that it can cope with the most difficult type of faults, potentially affecting all components of the network (both its links and nodes), and that it is simultaneously robust and efficient.