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(dlog ^{2} n+klog^{3} 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 (n ^{2})* 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