text:
\section{Introduction}
\label{sec:intro}

Mainstream disk drives are known to be susceptible to both
{\em device failures} \cite{Pinheiro07,Schroeder07} and
{\em sector failures} \cite{Bairavasundaram07,Schroeder10}: a device failure
implies the loss of all data in the failed device, while a sector failure
implies the data loss in a particular disk sector.  In particular, sector
failures are of practical concern not only in disk drives, but also in
emerging solid-state drives (SSDs) as they often appear as worn-out blocks after
frequent program/erase cycles \cite{Grupp09,Boboila10,Grupp12,Zheng13}.
In the face of device and sector failures, practical storage systems often
adopt {\em erasure codes} to provide data redundancy \cite{Plank13a}.
However, existing erasure codes often build on tolerating device failures and
provide device-level redundancy only.  To tolerate additional sector failures,
an erasure code must be constructed with extra parity
disks.  A representative example is RAID-6,
which uses two parity disks to tolerate one device failure together with one
sector failure in another non-failed device \cite{White10,Intel05}.
If the sector failures can span a number of devices, the same number of
parity disks must be provisioned.  Clearly, dedicating an entire parity disk
for tolerating a sector failure is too extravagant.

To tolerate both device and sector failures in a space-efficient
manner, sector-disk (SD) codes \cite{Plank13b,Plank13c} and the earlier PMDS
codes \cite{Blaum13a} (which are a subset of SD codes) have recently been
proposed.

Their idea is to introduce parity sectors, instead of entire parity disks, to
tolerate a given number of sector failures.  However, the constructions of
SD codes are known only for limited configurations (e.g., the number of
tolerable sector failures is no more than three), and some of the known
constructions rely on exhaustive searches \cite{Plank13b,Plank13c,Blaum13c}.

An open issue is to provide a general construction of erasure codes that can
efficiently tolerate both device and sector failures without any restriction
on the size of a storage array, the number of tolerable device failures, or
the number of tolerable sector failures.

In this paper, we make the first attempt to develop such a generalization,
which we believe is of great theoretical and practical interest to provide
space-efficient fault tolerance for today's storage systems.  After carefully
examining the assumption of SD codes on failure coverage, we find that
although SD codes have relaxed the assumption of the earlier PMDS codes to
comply with how most storage systems really fail, the assumption
remains too strict.  By reasonably relaxing the assumption of SD codes on
sector failure coverage, we construct a general family of erasure codes called
\emph{STAIR codes}, which efficiently tolerate both device and sector
failures.

Specifically, SD codes devote $s$ sectors per stripe to coding, and tolerate
the failure of any $s$ sectors per stripe.  We relax this assumption in STAIR
codes by limiting the number of devices that may simultaneously contain sector
failures, and by limiting the number of simultaneous sector failures per
device.

Consequently, as shown in
\S\ref{sec:problem}, STAIR codes are constructed to protect the sector failure
coverage defined by a vector $\mb{e}$, rather than all combinations of $s$
sector failures.

With the relaxed assumption, the construction of STAIR codes can be based on
existing erasure codes.  For example, STAIR codes can build on Reed-Solomon
codes (including standard Reed-Solomon codes \cite{Reed60,Plank97,Plank05} and
Cauchy Reed-Solomon codes \cite{Blomer95,Plank06}), which have no restriction
on code length and fault tolerance.

We first define some basic concepts and elaborate how the sector failure
coverage is formulated for STAIR codes in \S\ref{sec:problem}.  Then the paper
makes the following contributions:

\begin{itemize}
\item
We present a baseline construction of STAIR codes. Its idea is to run
two orthogonal encoding phases based on Reed-Solomon codes.
See \S\ref{sec:construction}.
\item
We propose an {\em upstairs decoding} method, which systematically
reconstructs the lost data due to both device and sector failures. The proof
of fault tolerance of STAIR codes follows immediately from the decoding
method. See \S\ref{sec:recovery}.
\item
Inspired by upstairs decoding, we extend the construction of STAIR codes to
regularize the code structure.  We propose two encoding
methods: {\em upstairs encoding} and {\em downstairs encoding}, both of which
reuse computed parity results in subsequent encoding.  The two encoding
methods provide complementary performance advantages for different
configuration parameters.  See \S\ref{sec:transformation}.
\item
We extensively evaluate STAIR codes in terms of space saving, encoding/decoding
speed, and update cost.  We show that STAIR codes achieve significantly higher
encoding/decoding speed than SD codes through parity reuse.  Most importantly,
we show the versatility of STAIR codes in supporting any size of a storage
array, any number of tolerable device failures, and any number of tolerable
sector failures.  See \S\ref{sec:evaluation}.
\item
We develop analytical models to characterize the reliability of STAIR codes
and discuss how the sector failure coverage of STAIR codes should be
configured.  We examine both independent and correlated sector failure models,
and show that it is critical for STAIR codes to support a wider range of
configurations in the presence of sector failure bursts discovered in the
field \cite{Bairavasundaram07,Schroeder10}. See \S\ref{sec:reliability}.
\end{itemize}

We review related work in \S\ref{sec:related}, and conclude this paper in
\S\ref{sec:conclusions}.


TITLE: closed balls are connected when its given the topology on $k$ given by non archimedian abosolute value?
QUESTION [1 upvotes]: Is it true that closed balls are connected when its given the topology on $k$ given by non archimedian abosolute value ?
I've shown if $k=\mathbb{Q}_{p}$ then we can write any closed ball as disjoint union of open balls and as open balls are also closed in this topology, so closed balls are actually disconnected. Here advantage was I could actually extract maximum powers of $p$ and could show, but here I don't have any advantage like that.

REPLY [2 votes]: Let $|\cdot|$ be a non-Archimedean absolute value on $k$, and define the associated metric
$$d:k\times k\to\Bbb R:\langle x,y\rangle\mapsto|x-y|\;.$$
For any $x,y,z\in k$ we have
$$\begin{align*}
d(x,y)&=|x-y|\\
&=|(x-z)+(z-y)|\\
&\le\max\{|x-z|,|z-y|\}\\
&=\max\{d(x,z),d(z,y)\}\;,
\end{align*}$$
i.e., $d$ is a non-Archimedean metric (or ultrametric).
For $r\in\Bbb R^+$ and $x\in k$ let
$$B(x,r)=\{y\in k:d(x,y)<r\}$$
and
$$\overline{B}(x,r)=\{y\in k:d(x,y)\le r\}\;;$$
Of course $\overline{B}(x,r)$ is closed; I’ll show that it’s also open. Suppose that $y\in\overline{B}(x,r)$. If $z\in B(y,r)$, then
$$d(x,z)\le\max\{d(x,y),d(y,z)\}\le r\;,$$
so $z\in\overline{B}(x,r)$. Thus, $B(y,r)\subseteq\overline{B}(x,r)$, and $$\overline{B}(x,r)=\bigcup_{y\in\overline{B}(x,r)}B(y,r)$$ is open.
Now suppose that $\overline{B}(x,r)\ne\{x\}$, so that there is a $y\in\overline{B}(x,r)\setminus\{x\}$. Let $s=\frac12d(x,y)$; then $B(x,s)$ is a non-empty clopen proper subset of $\overline{B}(x,r)$, and $\overline{B}(x,r)$ is therefore not connected. Thus, $\overline{B}(x,r)$ is connected if and only if it’s the singleton $\{x\}$.
Since our non-Archimedean metric arises from a non-Archimedean absolute value, we can say a little more:

If $\inf\limits_{0\ne x\in k}|x|=0$, then for all $x\in k$ and $r>0$ the closed ball $\overline{B}(x,r)$ is not connected.


TITLE: If $\sigma_n=\frac{s_1+s_2+\cdots+s_n}{n}$ then $\operatorname{{lim sup}}\sigma_n \leq \operatorname{lim sup} s_n$
QUESTION [16 upvotes]: This is a question from the book Methods of Real Analysis by R. R. Goldberg.

If $(s_n)$ is a sequence of real numbers and if $$\sigma_n=\frac{s_1+s_2+\cdots+s_n}{n}$$ then prove that: $\operatorname{{lim sup}}\sigma_n \leq \operatorname{lim sup} s_n$.

I don't have any idea how to start working on this problem. Please help. Thanks.

REPLY [2 votes]: [I've been working through Goldberg myself and found this question looking for an explanation myself. I think I eventually figured it out.]
Since this is from Goldberg, I'll point out that the problem statement suggests using his Theorem 2.9L, which essentially uses the interpretation in this Wikipedia article as an alternate definition of $\limsup$ and $\liminf$:

$\limsup_{n\to \infty} s_n = M$ means for any $\epsilon > 0$, (a) $s_n < M + \epsilon$ for all but a finite number of values of $n$; (b) $s_n > M - \epsilon$ for infinitely many values of $n$
(omitted similar def. for $\liminf$).

(He mentions it's an if and only if relationship, while only proving the "if" direction.)
If you peek ahead a bit to 2.11B, Goldberg happens to prove some things about Cesàro summability $(C,1)$, and you get very close to the desired proof because he uses the same technique he hinted at in this problem.
For the particular problem, by his alternate definition, for some $N_0$, $s_n < M + \epsilon$ if $n > N_0$ (and similarly, for some $N_1$, all $s_n < M + \frac{\epsilon}{2}$ if $n > N_1$).
Can we get $\sigma_n$ to eventually fit below $M + \epsilon$ too?
Proceeding as in the accepted answer and splitting the sum into two, the ultimately goal becomes finding a large enough $N_2$ such that $\sigma_n$ (which equals the sum of those two sums) is also smaller than $M + \epsilon$ (for arbitrary $\epsilon$ and all $n > N_2$).
An image may help motivate this:

The intuition is to "leave some room" between $M + \frac{\epsilon}{2}$ and $M + \epsilon$ such that the sum of the portions for the lower-indexed $s_i$ in $\sigma_n$ can be balanced out in some portion of the $\frac{\epsilon}{2}$-high strip extending from $N_1$ out to infinity.
(Here I'm thinking of the discrete sums as analogous to areas: can the area before $N_1$ fit into the area between $M+\frac{\epsilon}{2}$ and $M+\epsilon$? The answer seems pretty clearly yes to me based on the picture, but I still have to demonstrate the existence of some $N_2$ that works.)
The following reasoning seems to work (at least if $M \ge 0$, which can probably be made more rigorous for by translating each term of the sequence up by a well chosen constant and then undoing that later):
\begin{align}
\sigma_n &= \frac{1}{n}\sum_{i=1}^{N_1}s_i + \frac{1}{n}\sum_{i=N_1+1}^n s_i \\\\
 &\le \frac{N_1}{n}\max_{1\le i\le N_1}|s_i| + \frac{n-N_1}{n}(M + \frac{\epsilon}{2}) \\\\
 &= M + \frac{\epsilon}{2} - \frac{N_1}{n}(M + \frac{\epsilon}{2}) + \frac{N_1}{n}\max_{1\le i\le N_1}|s_i|
\end{align}
Doing some messy math we want to get the sum of the last two terms to be less than $\frac{\epsilon}{2}$ so that the whole $\sigma_n \le M + \epsilon$ (and therefore $\limsup_{n\to \infty} \sigma_n \le M$). Any $n \ge N_2 = \lceil\frac{2N_1}{\epsilon}(\max_{1\le i\le N_1}|s_i| - M - \frac{\epsilon}{2})\rceil$ seems to fit the bill.


TITLE: Find the differential equation given a fundamental set with no exponential name
QUESTION [0 upvotes]: My question is, given the general solution
 $$Y=C_1x+c_2\dfrac{1}{x}$$
find the differential equation
My attempt:
I have derivated the equation and then look for the constants:
$$Y'=C_1+c_2\dfrac{-1}{x^2}$$
$$Y''=c_2\dfrac{2}{x^3}$$
so $c_2=y''\dfrac{x^3}{2}$
and substitute in $y'$:
$$c_1=y'+\dfrac{y''x}{2}$$
then
$$y=(y'+\dfrac{y''x}{2})x+(y''\dfrac{x^3}{2})(\dfrac{1}{x})$$
and the equation its suppose to be
$$y''x^2+y'x=0$$
but when i solve it, it doesn't check with the general solution given, so, can someone please tell me what I'm doing wrong?
Thanks.

REPLY [0 votes]: Note that
$$
xy'=c_1x-\frac{c_2}x
$$
which is the given solution up to a sign change. Thus repeating this combination of operations
$$
x(xy')'=c_1x+\frac{c_2}x
$$
returns the original solution. Thus the differential equation is
$$
0=x(xy')'-y=x^2y''+xy'-y.
$$


TITLE: Inequality relating entropy to mutual information
QUESTION [2 upvotes]: Let $\{X_n\}$ be a sequence of independent, discrete random variables, and let $Z$ be another discrete random variable. Show that $$H(Z)\geq\sum_{i=1}^\infty I(X_i;Z)$$ where $H$ is the entropy and $I$ is the mutual information.
I really don't know where to start with this. Of course there is the basic fact (practically by definition) that $H(Z)\geq I(X_i;Z)$ for each $i$ but I don't see how to improve this, especially since we're given practically no information about the relationship between $\{X_n\}$ and $Z$.
UPDATE ON ATTEMPT: Fix $n\geq1$. Then by the chain rule for mutual information $$I(X_1^n;Z)=\sum_{k=1}^nI(X_k;Z|X_1^{k-1}).$$ Then we have by definition $$I(X_k;Z|X_1^{k-1})=H(X_k|X_1^{k-1})-H(X_k|Z,X_1^{k-1}).$$ Because of the independence of the $X_i$, $H(X_k|X_1^{k-1})=H(X_k)$. If we have $H(X_k|Z,X_1^{k-1})=H(X_k|Z)$ then we have shown that for any $n\geq1$ we have $$I(X_1^n;Z)=\sum_{k=1}^nI(X_k;Z).$$ Using the fact that $H(Z)\geq I(X_1^n;Z)$ then gives the result (I think) when taking $n\to\infty$ (although this feels a bit iffy to me).
However the equality $H(X_k|Z,X_1^{k-1})=H(X_k|Z)$ is true if and only if $X_k$ and $X_1^{k-1}$ are conditionally independent given $Z$. I don't think that this is necessarily true, so is there a problem with my approach?

REPLY [1 votes]: It suffices to show that, if $X,Y,Z$ are discrete random variables with $Y, Z$ independent, then
$$I(X; Y, Z) \geq I(X; Y) + I(X; Z).$$
This is equivalent to
$$H(X) + H(Y, Z) - H(X, Y, Z) \geq 2H(X) + H(Y) + H(Z) - H(X, Y) - H(X, Z).$$
As $H(Y, Z) = H(Y) + H(Z)$, this is equivalent to
$$ H(X, Y, Z) + H(X) \leq  H(X, Y) + H(X, Z)$$
or
$$ H(Y | X, Z)  \leq  H(Y | X)$$
which holds as conditioning on more variables decreases entropy.
Anyways, iterating our claim give
$$\sum_{i = 1}^n I(Z; X_i) \leq I(Z; X_1,\cdots, X_n) \leq H(Z)$$
and taking $n \to \infty$ gives the desired result.


TITLE: All repeated integrals on $(-1,1)$ vanishing for a non-zero function?
QUESTION [1 upvotes]: Is it possible to find a non-zero function $f(x)$ on $(-1,1)$ such that all its repeated integrals vanish?
By repeated integrals I mean sequence of numbers $$ I_n =f^{(-n)}(1)-f^{(-n)}(-1) $$ with
$$ \frac{d}{dx}f^{(-n-1)} = f^{(-n)} \text{ and } f^{(-n-1)}(-1)=0.$$
I have suspition such function might exist, something similar to $$\mathrm{sin}(\frac{x}{x^2-1})$$ but I am unable to find an actual example with proof.

REPLY [2 votes]: No, $f$ is necessarily zero (almost everywhere). We have
$$I_n=\frac{1}{(n-1)!}\int_{-1}^{1}(1-x)^{n-1}f(x)\,dx$$
(easily proven using integration by parts), thus if these are all zeros then
$$\int_{-1}^{1}f(x)p(x)\,dx=0$$
for any polynomial $p(x)$, and we proceed by the density of polynomials.


TITLE: Why does achieving a $O(1/k^2)$ upper bound for first-order methods imply acceleration?
QUESTION [0 upvotes]: I was watching a talk of Michael Jordan on Youtube. In the lecture, he mentioned that for a convex-Lipschitz function $f$, the gradient descent
$$x^{k+1} = x^k - \beta \nabla f(x^k)$$ for a constant step-size achieves the following rate,
$$f(x^k) - f(x^*) \leq O(1/k)$$
where $x^*$ is a local minimizer of $f$.
And Nesterov came up with an accelerated version,
$$y^{k+1} = x^k - \beta \nabla f(x^k)$$
$$x^{k+1} = (1-\lambda^k)x^{k+1} + \lambda^k y^k$$
which acheives the following upper bound
$$f(x^k) - f(x^*) \leq O(1/k^2)$$
At this point, I am terribly confused as to why this upper bound would imply acceleration. Consider the original argument given by Nesterov,

This theorem doesn't say anything about upper bound,  it is clearly a theorem on theoretical lower bound $\Omega(1/k^2)$ (unless that $\geq$ should have been a $\leq$). Furthermore, it is not a statement on the existence of a hypothetical algorithm, but that of a particular function. In fact, in the proof, Nesterov explicitly constructs the function that satisfies this condition. It doesn't say there exists an algorithm that achieves this lower bound. Also, there are strange conditions in the theorem such as $t \leq (n-1)/2$ that is never mentioned in the rate of convergence proofs of gradient descent, etc.
I guess I would be more convinced if the result instead was stated as follows: "Prop: there exists a first-order method such that for convex-Lipschitz functions, achieves $f(x^k) - f(x^*) \leq O(1/k^2)$". This seems to be a more logically coherent motivation as to why the rate for gradient descent is suboptimal. However, this is not what the theorem says and I don't see how the theorem implies this proposition.... (as in comment)
Therefore, in order to show that an algorithm achieves acceleration, we must show that it achieves a lower bound of $\Omega(1/k^2)$. So why is that in $>99\%$ of the literature on accelerated algorithms, an upper bound is provided instead of a lower bound?
Plus, an upper bound means the "worst-case" upper bound. Therefore, even if we do show the gradient descent achieves $O(1/k)$ rate, unless that $1/k$ rate is tight, it does not mean that it will experience that worst-case rate in practice. Since all these rates are worst-case rates of convergence, what is preventing the gradient descent from vastly surpassing Nesterovs algorithm in practice?
Can someone please provide a simple argument why upper bound implies acceleration, when the acceleration result is stated neither in terms of an upper bound nor a statement regarding the existence of a particular "accelerated" algorithm.

REPLY [1 votes]: Nesterov's theorem that you quoted is showing that no algorithm of this type can do better than $O(1/k^2)$.  So a convergence rate of $O(1/k^2)$ is in some sense optimal for this type of algorithm. Nesterov separately provided an algorithm that actually achieves this optimal $O(1/k^2)$ convergence rate.
Of course, if the error decreases like $1/k^2$, that's a dramatic improvement over an algorithm for which the error goes down like $1/k$.


TITLE: what is domain of $f(x)=(-1)^x$
QUESTION [5 upvotes]: What exactly is the domain of the $$f(x)=(-1)^x$$
Because if $x=\pm0.5$ or $x=\pm0.25$ etc we get imaginary numbers.
But if we take $x=\pm\frac{1}{3}$ we get a real number, so how to define its domain?
Do we restrict it to only integers?

REPLY [7 votes]: There is no problem in defining such a function over the rational numbers that can be represented with an odd denominator. However such a function will not obey the standard rules for exponentials:
$$
(-1)^{1/3}=-1
$$
but, on the other hand,
$$
((-1)^{2/1})^{1/6}=1
$$
The usefulness of such a function is unclear.
However, you can define it as a multivalued function over the complex numbers, using the fact that $-1=e^{i\pi+2ki\pi}$ ($k$ any integer)
$$
(-1)^x=e^{(2k+1)ix\pi}
$$
Note that in general this will have infinitely many values, unless $x$ is rational. If $x$ is rational and $x=a/b$, with odd $b$, then only one of the values will be real and, conversely, if one of the values is real, then $x$ is rational and $x=a/b$ with odd $b$. (Exercise on complex numbers.)