
We consider a communication channel in which the only possible communication
mode is transmitting beeps, which reach all the nodes instantaneously. Nodes
are anonymous, in that they do not have any individual identifiers. The
algorithmic goal is to randomly assign names to the nodes in such a manner that
the names make a contiguous segment of positive integers starting from $1$. We
give a Las Vegas naming algorithm for the case when the number of nodes $n$ is
known, and a Monte Carlo algorithm for the case when the number of nodes $n$ is
not known. The algorithms are provably optimal with respect to the expected
time $O(n\log n)$, the number of used random bits $O(n\log n)$, and the
probability of error.

We consider singlehop radio networks with multiple channels as a model of
wireless networks. There are $n$ stations connected to $b$ radio channels that
do not provide collision detection. A station uses all the channels
concurrently and independently. Some $k$ stations may become active
spontaneously at arbitrary times. The goal is to wake up the network, which
occurs when all the stations hear a successful transmission on some channel.
Duration of a wakingup execution is measured starting from the first
spontaneous activation. We present a deterministic algorithm for the general
problem that wakes up the network in $O(k\log^{1/b} k\log n)$ time, where $k$
is unknown. We give a deterministic scalable algorithm for the special case
when $b>d \log \log n$, for some constant $d>1$, which wakes up the network in
$O(\frac{k}{b}\log n\log(b\log n))$ time, with $k$ unknown. This algorithm
misses time optimality by at most a factor of $O(\log n(\log b +\log\log n))$,
because any deterministic algorithm requires $\Omega(\frac{k}{b}\log
\frac{n}{k})$ time. We give a randomized algorithm that wakes up the network
within $O(k^{1/b}\ln \frac{1}{\epsilon})$ rounds with a probability that is at
least $1\epsilon$, for any $0<\epsilon<1$, where $k$ is known. We also
consider a model of jamming, in which each channel in any round may be jammed
to prevent a successful transmission, which happens with some known parameter
probability $p$, independently across all channels and rounds. For this model,
we give two deterministic algorithms for unknown~$k$: one wakes up the network
in time $O(\log^{1}(\frac{1}{p})\, k\log n\log^{1/b} k)$, and the other in
time $O(\log^{1}(\frac{1}{p}) \, \frac{k}{b} \log n\log(b\log n))$ but
assuming the inequality $b>\log(128b\log n)$, both with a probability that is
at least $11/\mbox{poly}(n)$.

We consider wireless networks with the SINR model of interference when nodes
have very limited individual knowledge and capabilities. In particular, nodes
do not know their geographic coordinates and their neighborhoods, nor even the
size $n$ of the network, nor can they sense collisions. Each node is equipped
only with a unique integer name, where $N$ is an upper bound on their range. We
study distributed algorithms for communication problems in the following three
settings. In the singlenodestart case, when one node starts an execution and
the other nodes are awoken by receiving messages from already awoken nodes, we
present a randomized broadcast algorithm which wakes up all the nodes in $O(n
\log^2 N)$ rounds with high probability. Let $\Delta$ denote the maximum number
of nodes that successfully receive a message transmitted by a node when no
other nodes transmit. For the synchronizedstart case, when all the nodes start
an execution simultaneously, we give a randomized algorithm that computes a
backbone of the network in $O(\Delta\log^{7} N)$ rounds with high probability.
Finally, in the partlycoordinatedstart case, when a number of nodes start an
execution together and other nodes are awoken by receiving messages from the
already awoken nodes, we develop an algorithm that creates a backbone network
in time $O(n\log^2 N +\Delta\log^{7} N)$ with high probability.

We consider the DoAll problem, where $p$ cooperating processors need to
complete $t$ similar and independent tasks in an adversarial setting. Here we
deal with a synchronous message passing system with processors that are subject
to crash failures. Efficiency of algorithms in this setting is measured in
terms of work complexity (also known as total available processor steps) and
communication complexity (total number of pointtopoint messages). When work
and communication are considered to be comparable resources, then the overall
efficiency is meaningfully expressed in terms of effort defined as work +
communication. We develop and analyze a constructive algorithm that has work
$O( t + p \log p\, (\sqrt{p\log p}+\sqrt{t\log t}\, ) )$ and a nonconstructive
algorithm that has work $O(t +p \log^2 p)$. The latter result is close to the
lower bound $\Omega(t + p \log p/ \log \log p)$ on work. The effort of each of
these algorithms is proportional to its work when the number of crashes is
bounded above by $c\,p$, for some positive constant $c < 1$. We also present a
nonconstructive algorithm that has effort $O(t + p ^{1.77})$.

We study deterministic distributed broadcasting in synchronous
multipleaccess channels. Packets are injected into $n$ nodes by a windowtype
adversary that is constrained by a window $w$ and injection rates individually
assigned to all nodes. We investigate what queue size and packet latency can be
achieved with the maximum aggregate injection rate of one packet per round,
depending on properties of channels and algorithms. We give a nonadaptive
algorithm for channels with collision detection and an adaptive algorithm for
channels without collision detection that achieve $O(\min(n+w,w\log n))$ packet
latency. We show that packet latency has to be either $\Omega(w \max (1,\log_w
n))$, when $w\le n$, or $\Omega(w+n)$, when $w>n$, as a matching lower bound to
these algorithms. We develop a nonadaptive algorithm for channels without
collision detection that achieves $O(n+w)$ queue size and $O(nw)$ packet
latency. This is in contrast with the adversarial model of global injection
rates, in which nonadaptive algorithms with bounded packet latency do not
exist (Chlebus et al. Distributed Computing 22(2): 93  116, 2009). Our
algorithm avoids collisions produced by simultaneous transmissions; we show
that any algorithm with this property must have $\Omega(nw)$ packet latency.

We study broadcast in multiple access channels in dynamic adversarial
settings. There is an unbounded supply of anonymous stations attached to a
synchronous channel. There is an adversary who injects packets into stations to
be broadcast on the channel. The adversary is restricted by injection rate,
burstiness, and by how many passive stations can be simultaneously activated by
providing them with packets. We consider deterministic distributed broadcast
algorithms, which are further categorized by their properties. We investigate
for which injection rates can algorithms attain bounded packet latency, when
adversaries are restricted to be able to activate at most one station per
round. The rates of algorithms we present make the increasing sequence
consisting of $\frac{1}{3}$, $\frac{3}{8}$ and $\frac{1}{2}$, reflecting the
additional features of algorithms. We show that injection rate $\frac{3}{4}$
cannot be handled with bounded packet latency.

We study broadcasting in multiple access channels with dynamic packet
arrivals and jamming. Communication environments are represented by adversarial
models that specify constraints on packet arrivals and jamming. We consider
deterministic distributed broadcast algorithms and give upper bounds on the
worstcase packet latency and the number of queued packets in relation to the
parameters defining adversaries. Packet arrivals are determined by a rate of
injections and a number of packets that can be generated in one round. Jamming
is constrained by a rate with which an adversary can jam rounds and by a number
of consecutive rounds that can be jammed.

We consider Parallel Random Access Machine (PRAM) which has some processors
and memory cells faulty. The faults considered are static, i.e., once the
machine starts to operate, the operational/faulty status of PRAM components
does not change. We develop a deterministic simulation of a fully operational
PRAM on a similar faulty machine which has constant fractions of faults among
processors and memory cells. The simulating PRAM has $n$ processors and $m$
memory cells, and simulates a PRAM with $n$ processors and a constant fraction
of $m$ memory cells. The simulation is in two phases: it starts with
preprocessing, which is followed by the simulation proper performed in a
stepbystep fashion. Preprocessing is performed in time $O((\frac{m}{n}+ \log
n)\log n)$. The slowdown of a stepbystep part of the simulation is $O(\log
m)$.

The problem of finding a spanning forest of a graph in a
distributedprocessing environment is studied. If an input graph is weighted,
then the goal is to find a minimumweight spanning forest. The processors
communicate by broadcasting. The output consists of the edges that make a
spanning forest and have been broadcast on the network. Input edges are
distributed among the processors, with each edge held by one processor.
The underlying broadcast network is implemented as a multipleaccess channel.
If exactly one processor attempts to perform a broadcast, then the broadcast is
successful. A message broadcast successfully is delivered to all the processors
in one step. If more than one processors broadcast simultaneously, then the
messages interfere with each other and no processor can receive any of them.
Optimality of algorithmic solutions is investigated, by way of comparing
deterministic with randomized algorithms, and adaptive with oblivious ones.
Lower bounds are proved that either justify the optimality of specific
algorithms or show that the optimal performance depends on a class of
algorithms.

A communication network is called a radio network if its nodes exchange
messages in the following restricted way. First, a send operation performed by
a node delivers copies of the same message to all directly reachable nodes.
Secondly, a node can successfully receive an incoming message only if exactly
one of its neighbors sent a message in that step. It is this semantics of how
ports at nodes send and receive messages that defines the networks rather than
the fact that only radio waves are used as a medium of communication; but if
that is the case then just a single frequency is used. We discuss algorithmic
aspects of exchanging information in such networks, concentrating on
distributed randomized protocols. Specific problems and solutions depend a lot
on the topology of the underlying reachability graph and how much the nodes
know about it. In singlehop networks each pair of nodes can communicate
directly. This kind of networks is also known as the multiple access channel.
Popular broadcasting protocols used on such channels are Aloha and the
exponential backoff. Multihop networks may have arbitrary topology and packets
need to be routed hopping through a sequence of adjacent nodes. Distributed
protocols run by such networks are usually robust enough not to expect the
nodes to know their neighbors. These adhoc networks and protocols model the
situation when nodes are mobile and do not rely on a fixed infrastructure.

We consider deterministic distributed broadcasting on multiple access
channels in the framework of adversarial queuing. Packets are injected
dynamically by an adversary that is constrained by the injection rate and the
number of packets that may be injected simultaneously; the latter we call
burstiness. The maximum injection rate that an algorithm can handle in a stable
manner is called the throughput of the algorithm. We develop an algorithm that
achieves throughput $1$ for any number of stations against leakybucket
adversaries. The algorithm has $O(n^2+\text{burstiness})$ packets queued
simultaneously at any time, where $n$ is the number of stations; this upper
bound is proved to be best possible. An algorithm is called fair when each
packet is eventually broadcast. We show that no algorithm can be both stable
and fair for a system of at least two stations against leakybucket
adversaries. We study in detail small systems of exactly two and three stations
against window adversaries to exhibit differences in quality of broadcast among
classes of algorithms. For two stations, we show that fair latency can be
achieved by a full sensing algorithm, while there is no stable acknowledgment
based algorithm. For three stations, we show that fair latency can be achieved
by a general algorithm, while no full sensing algorithm can be stable. Finally,
we show that algorithms that either are fair or do not have the queue sizes
affect the order of transmissions cannot be stable in systems of at least four
stations against window adversaries.

We consider synchronous distributed systems in which anonymous processors
communicate by shared readwrite variables. The goal is to have all the
processors assign unique names to themselves. We consider the instances of this
problem determined by whether the number $n$ is known or not, and whether
concurrently attempting to write distinct values into the same memory cell is
allowed or not, and whether the number of shared variables is a constant
independent of $n$ or it is unbounded. For known $n$, we give Las Vegas
algorithms that operate in the optimum expected time, as determined by the
amount of available shared memory, and use the optimum $O(n\log n)$ expected
number of random bits. For unknown $n$, we give Monte Carlo algorithms that
produce correct output upon termination with probabilities that are
$1n^{\Omega(1)}$, which is best possible when terminating almost surely and
using $O(n\log n)$ random bits.

In this article we introduce a new model to study stability in multihop
wireless networks in the framework of adversarial queueing. In such a model, a
routing protocol consists of three components: a transmission policy, a
scheduling policy to select the packet to transmit form a set of packets parked
at a node, and a hearing control mechanism to coordinate transmissions with
scheduling. For such a setting, we propose a definition of universal stability
that takes into account not only the scheduling policies (as in the standard
wireline adversarial model), but also the transmission policies. First, we show
that any scheduling policy that is unstable in the classical wireline
adversarial model remains unstable in the multihop radio network model, even
in scenarios free of inter ferences. Then, we show that both SIS and LIS (two
wellknown universally stable scheduling policies in the wireline adversarial
model) remain stable in the multihop radio network model, provided a proactive
hearing control is used. In contrast, such scheduling policies turn out to be
unstable when using a reactive hearing control. However, the scheduling policy
LIS can be enforced to be universally stable provided ties are resolved in a
permanent manner. Such a situation doesn't hold in the case of SIS, which
remains unstable regardless of how ties are resolved. Furthermore, for some
transmission policies which we call regular, we also show that all scheduling
policies that are universally stable when using proactive hearing control
(which include SIS and LIS) remain universally stable when using reactive
hearing control.

An asynchronous system of $n$ processes prone to crashes, along with a number
of shared readwrite registers, is the distributed setting. We consider
assigning integer numbers to processes in an exclusive manner, in the sense
that no integer is assigned to two distinct processes. In the problem called
Renaming, any $k\le n$ processes, which hold original names from a range
$[N]=\{1,\ldots,N\}$, contend to acquire unique integers in a smaller range
$[M]$ as new names using some $r$ auxiliary shared registers. We develop a
waitfree $(k,N)$renaming solution operating in $O(\log k (\log N + \log
k\log\log N))$ local steps, for $M=O(k)$, and with $r=O(k\log(N/k))$ auxiliary
registers. We develop a waitfree $k$renaming algorithm operating in $O(k)$
time, with $M=2k1$ and with $r=O(k^2)$ registers. We develop an almost
adaptive waitfree $N$renaming algorithm, with $N$ known, operating in
$O(\log^2 k (\log N + \log k\log\log N))$ time, with $M=O(k)$ and with
$r=O(n\log(N/n))$ registers. We give a fully adaptive solution of Renaming,
with neither $k$ nor $N$ known, having $M=8k\lg k1$ as the bound on new
names, operating in $O(k)$ steps and using $O(n^2)$ registers. As regards lower
bounds, we show that a waitfree solution of Renaming requires
$1+\min\{k2,\log_{2r} \frac{N}{2M}\}$ steps in the worst case. We apply
renaming algorithms to obtain solutions to a problem called StoreandCollect,
which is about operations of storing and collecting under additional
requirements. We consider the problem called UnboundedNaming in which
processes may repeatedly request new names, while no name can be reused once
assigned, so that infinitely many integers need to be exclusively assigned as
names in an execution.