• ### Naming a Channel with Beeps(1608.04174)

Dec. 28, 2018 cs.DC, cs.NI
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.
• ### Scalable Wake-up of Multi-Channel Single-Hop Radio Networks(1411.4498)

Dec. 26, 2018 cs.DS
We consider single-hop 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 waking-up 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 $1-1/\mbox{poly}(n)$.
• ### Anonymous Processors with Synchronous Shared Memory(1507.02272)

Sept. 1, 2016 cs.DC
We consider synchronous distributed systems in which anonymous processors communicate by shared read-write 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 $1-n^{-\Omega(1)}$, which is best possible when terminating almost surely and using $O(n\log n)$ random bits.
• ### A Distributed Message-Optimal Assignment on Rings(1502.02427)

Sept. 9, 2015 cs.DS
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.
• ### Computing Majority with Triple Queries(1105.1622)

May 9, 2011 cs.DS
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 3-queries 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.