
A linear block code with dimension $k$, length $n$, and minimum distance $d$
is called a locally repairable code (LRC) with locality $r$ if it can retrieve
any coded symbol by at most $r$ other coded symbols. LRCs have been recently
proposed and used in practice in distributed storage systems (DSSs) such as
Windows Azure storage and Facebook HDFSRAID. Theoretical bounds on the maximum
locality of LRCs ($r$) have been established. The \textit{average} locality of
an LRC ($\overline{r}$) directly affects the costly repair bandwidth, disk I/O,
and number of nodes involved in the repair process of a missing data block.
There is a gap in the literature studying $\overline{r}$. In this paper, we
establish a lower bound on $\overline{r}$ of arbitrary $(n,k,d)$ LRCs.
Furthermore, we obtain a tight lower bound on $\overline{r}$ for a practical
case where the code rate $(R=\frac{k}{n})$ is greater than
$(1\frac{1}{\sqrt{n}})^2$. Finally, we design three classes of LRCs that
achieve the obtained bounds on $\overline{r}$. Comparing with the existing
LRCs, our proposed codes improve the average locality without sacrificing such
crucial parameters as the code rate or minimum distance.

For a systematic erasure code, update complexity (UC) is defined as the
maximum number of parity blocks needed to be changed when some information
blocks are updated. Locally repairable codes (LRCs) have been recently proposed
and used in realworld distributed storage systems. In this paper, update
complexity for optimal LRC is studied and both lower and upper bounds on UC are
established in terms of length (n), dimension (k), minimum distance (d), and
locality (r) of the code, when (r+1)n. Furthermore, a class of optimal LRCs
with small UC is proposed. Our proposed LRCs could be of interest as they
improve UC without sacrificing optimality of the code.

We derive a simple lower bound for the multiversion coding problem
formulated in [1]. We also propose simple algorithms that almost match the
lower bound derived. Another lower bound is proven for an extended version of
the multiversion coding problem introduced in [2].

The broadcast throughput in a network is defined as the average number of
messages that can be transmitted per unit time from a given source to all other
nodes when time goes to infinity.
Classical broadcast algorithms treat messages as atomic tokens and route them
from the source to the receivers by making intermediate nodes store and forward
messages. The more recent network coding approach, in contrast, prompts
intermediate nodes to mix and code together messages. It has been shown that
certain wired networks have an asymptotic network coding gap, that is, they
have asymptotically higher broadcast throughput when using network coding
compared to routing. Whether such a gap exists for wireless networks has been
an open question of great interest. We approach this question by studying the
broadcast throughput of the radio network model which has been a standard
mathematical model to study wireless communication.
We show that there is a family of radio networks with a tight $\Theta(\log
\log n)$ network coding gap, that is, networks in which the asymptotic
throughput achievable via routing messages is a $\Theta(\log \log n)$ factor
smaller than that of the optimal network coding algorithm. We also provide new
tight upper and lower bounds that show that the asymptotic worstcase broadcast
throughput over all networks with $n$ nodes is $\Theta(1 / \log n)$
messagesperround for both routing and network coding.

We present a randomized distributed algorithm that in radio networks with
collision detection broadcasts a single message in $O(D + \log^6 n)$ rounds,
with high probability. This time complexity is most interesting because of its
optimal additive dependence on the network diameter $D$. It improves over the
currently best known $O(D\log\frac{n}{D}\,+\,\log^2 n)$ algorithms, due to
Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These
algorithms where designed for the model without collision detection and are
optimal in that model. However, as explicitly stated by Peleg in his 2007
survey on broadcast in radio networks, it had remained an open question whether
the bound can be improved with collision detection.
We also study distributed algorithms for broadcasting $k$ messages from a
single source to all nodes. This problem is a natural and important
generalization of the singlemessage broadcast problem, but is in fact
considerably more challenging and less understood. We show the following
results: If the network topology is known to all nodes, then a $k$message
broadcast can be performed in $O(D + k\log n + \log^2 n)$ rounds, with high
probability. If the topology is not known, but collision detection is
available, then a $k$message broadcast can be performed in $O(D + k\log n +
\log^6 n)$ rounds, with high probability. The first bound is optimal and the
second is optimal modulo the additive $O(\log^6 n)$ term.

We consider the wellstudied radio network model: a synchronous model with a
graph G=(V,E) with V=n where in each round, each node either transmits a
packet, with length B=Omega(log n) bits, or listens. Each node receives a
packet iff it is listening and exactly one of its neighbors is transmitting. We
consider the problem of kmessage broadcast, where k messages, each with
Theta(B) bits, are placed in an arbitrary nodes of the graph and the goal is to
deliver all messages to all the nodes. We present a simple proof showing that
there exist a radio network with radius 2 where for any k, broadcasting k
messages requires at least Omega(k log n) rounds. That is, in this network,
regardless of the algorithm, the maximum achievable broadcast throughput is
O(1/log n).

The interference at a wireless node s can be modelled by the number of
wireless nodes whose transmission ranges cover s. Given a set of positions for
wireless nodes, the interference minimization problem is to assign a
transmission radius (equivalently, a power level) to each node such that the
resulting communication graph is connected, while minimizing the maximum
interference. We consider the model introduced by von Rickenback et al. (2005),
in which each transmission range is represented by a ball and edges in the
communication graph are symmetric. The problem is NPcomplete in two dimensions
(Buchin 2008) and no polynomialtime approximation algorithm is known.
Furthermore, even in one dimension (the highway model), the problem's
complexity is unknown and the maximum interference of a set of n wireless nodes
can be as high as Theta(sqrt(n)) (von Rickenback et al. 2005). In this paper we
show how to solve the problem efficiently in settings typical for wireless ad
hoc networks. In particular, we show that if node positions are represented by
a set P of n points selected uniformly and independently at random over a
ddimensional rectangular region, for any fixed d, then the topology given by
the closure of the Euclidean minimum spanning tree of P has maximum
interference O(log n) with high probability. We extend this bound to a general
class of communication graphs over a broad set of probability distributions.
Next we present a local algorithm that constructs a graph from this class; this
is the first local algorithm to provide an upper bound on the expected maximum
interference. Finally, we discuss an empirical evaluation of our algorithm with
a suite of simulation results.