
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 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.

Consider a set of items and a set of $m$ colors, where each item is
associated to one color. Consider also $n$ computational agents connected by a
ring. Each agent holds a subset of the items and items of the same color can be
held by different agents. We analyze the problem of distributively assigning
colors to agents in such a way that (a) each color is assigned to one agent
only and (b) the number of different colors assigned to each agent is minimum.
Since any color assignment requires the items be distributed according to it
(e.g. all items of the same color are to be held by only one agent), we define
the cost of a color assignment as the amount of items that need to be moved,
given an initial allocation. We first show that any distributed algorithm for
this problem requires a message complexity of $\Omega(n\cdot m)$ and then we
exhibit an optimal message complexity algorithm for synchronous rings that in
polynomial time determines a color assignment with cost at most three times the
optimal. We also discuss solutions for the asynchronous setting. Finally, we
show how to get a better cost solution at the expenses of either the message or
the time complexity.

Consider a bin containing $n$ balls colored with two colors. In a $k$query,
$k$ balls are selected by a questioner and the oracle's reply is related
(depending on the computation model being considered) to the distribution of
colors of the balls in this $k$tuple; however, the oracle never reveals the
colors of the individual balls. Following a number of queries the questioner is
said to determine the majority color if it can output a ball of the majority
color if it exists, and can prove that there is no majority if it does not
exist. We investigate two computation models (depending on the type of replies
being allowed). We give algorithms to compute the minimum number of 3queries
which are needed so that the questioner can determine the majority color and
provide tight and almost tight upper and lower bounds on the number of queries
needed in each case.