\section{Introduction}
The main goal of the presented work is to explain a decay of the emergent time variability of X-ray emission in
compact  sources when these sources evolve from low/hard  (LH)
to high/soft  (HS)
states
[see \citet{rm06} and \citet{tsa07}, hereafter TSA07, for details of observations].  In particular,
power density spectrum (PDS) of black hole binaries in hard states is dominated by a component, which has
a specific shape roughly described by a broken power-law. The low-frequency part is mostly flat, while
the power-law  index $\alpha$
above the ``break'' frequency $\nu_{br}$ is variable between 1 and 2.  It is well established that the fractional root-mean-square (rms)
 variability in a source light curve decreases as a source evolves from LH state to HS state. Simultaneously, both $\nu_{br}$

 and $\alpha$

 increase. Although empirical shot-noise models were able to
describe in general the observed PDS shape \citep{fws05}, the physical picture explaining the observed evolution during spectral
transitions was missing. Moreover, shot-noise models were challenged by the linear absolute rms-flux relation
\citep{utt05,utt04}. This rms flux relation assumes that amplitudes and time-scales of shots are not independent, but
are related in some way.

\citet{L97}, hereafter L97,  was the first to suggest a model for this  time variability production in the accretion powered X-ray sources.
He  considered small amplitude local fluctuations in the accretion rate at each radius,
caused by small amplitude variations in the viscosity, and then studied  the effect of these fluctuations on the
accretion rate at the inner disc edge. His linear calculations show that if the characteristic time-scale of the viscosity
variations  is everywhere comparable to the viscous (inflow) time-scale, and
if the amplitude of the variations is independent of radius, then the power spectrum of luminosity fluctuations is a power-law
$1/\nu$.  If the amplitude of the variations increases with radius, the slope of the power spectrum of the luminosity variations
is steeper than 1. Lyubarskii pointed out that he had no physical model for the cause of such fluctuations.
\citet{utt05} pointed out that  rms-flux relation is naturally explained in the framework developed by Lyubarskii.

TSA07 formulated and solved the problem of local driving perturbation diffusion
in a ``disk-like'' configuration (which can be either a geometric thin Keplerian accretion disk or Compton cloud).  The problem of the diffusive propagation of the  space distributed  high-frequency
perturbations is formulated  as a  problem in terms of  the diffusion equation for  the surface density perturbations.
This equation is combined with the appropriate boundary conditions.
The formulation of this problem and its solution are  general and  classical.
The parameters of the resulting PDS,  diffusion time scale of the diffusion propagation of the
local perturbations $t_0$ and the power-law index of the viscosity distribution over radius,
are essential parameters of  diffusion in a given  bounded configuration.
In TSA07 we call our PDS model for the  Green's function of the bounded configuration as
a white-red noise (WRN) and we adopt  this
name throughout this paper.

The problem formulation was similar to the Lyubarskii's scheme.
However, the method of solution is different. Lyubarskii treated the factorization of the
driving term (i.e. separating it into two parts each depending on time and radius only) by
linearizing the system. In TSA07 the analytical solution  is obtained for  the case of the factorized driving sources. Then,
using the mean value theorem  we showed that the general solution is simply a convolution of the configuration response  signal (the Green's function)   and  the mean driving signal in the configuration.
Thus the resulting power spectrum of the X-ray signal, as a  convolution, is a product
of the power spectrum related to the  configuration Green's function  and that  related
to  the perturbation sources (sources of driving oscillations).

The PDS of the  Green's function is a white-red noise power spectrum (WRN).
 Specifically, the low frequency (LF) asymptotic form of the WRN PDS, when the frequency  is less than the inverse of   diffusion timescale in the ``disk-like'' configuration  $t_0^{-1}$,

 is characterized by a flat shoulder (white noise).
 In other words, the  LF white noise shoulder  is insensitive to the source and  viscosity distributions over radius.

 The high frequency (HF)  asymptotic form of WRN is a power law $\nu^{-\alpha}$ with
 index  $\alpha$, which is determined by the viscosity and perturbation source
 distributions over the accretion configuration. The index $\alpha=3/2$ when the viscosity {\it linearly} increases with radius and  the perturbation sources distribution  is quasi-uniform.
The basis of the presented power spectrum formation scenario is that  the timing signal of the WRN PDS shape  is a result of diffusive propagation of driving  perturbations in the bounded configuration (disk or Compton cloud)   in the same way as X-ray photon spectrum is a result of the photon diffusion  (namely, upscattering of seed photons) in the  same bounded configuration.

The driving oscillation amplitude is assumed to be a smooth function of the radius.
TSA07 suggested that driving fluctuations in the configuration
can be introduced by g-mode driving oscillations  at any given  annulus.
The local g-mode  driving  fluctuations,  produced possibly by  local  Rayleigh-Taylor local instabilities,
are  high-frequency damped quasi-periodic oscillations (QPOs)  which frequencies are related to the local Keplerian
frequencies. As we mentioned above TSA07 formulated and solved
a problem of the diffusive propagation of the  space distributed  high-frequency
perturbations in the bounded configuration.
Our diffusion model for PDS is a product of WRN PDS and the driving source PDS (Lorentzian).

The WRN PDS is  a power spectrum of the solution of the initial value (Cauchy) problem which
is   a linear superposition of exponential  shots [see \citet{{wo01}}].
For example, if the driving perturbations  are distributed  according to the first eigen-function of the diffusion operator
then the bounded medium works as a filter producing just one exponential shot as a result of the diffusive  propagation of eigen-function distribution of the seed  perturbations. In the general case the resulting signal is a linear
superposition of exponential shots which are  {\it related} to the appropriate eigen-functions.
Furthermore,
TSA07 demonstrate that  {\it the observed rms-flux relations} [e.g. \citet{utt05}]
 is naturally explained by our diffusion model.  In the framework of the linear diffusion theory  the emergent
perturbations are always linearly related to the driving source perturbations through a convolution of the configuration Green's  function and  source distribution.

An important  question is  what our diffusion model predicts for relative contributions of the WRN PDS,  the driving  oscillation PDS in the resulting PDS and for a dependence of the integrated PDS power
on  the driving oscillation frequency.
The next question is   how this model dependence of the integrated power
vs the driving oscillation frequency
is related to the observed dependence of that.
The answers to these questions  are the points   of the presented study.

In \S 2 we refer to   details  of Cyg X-1 observations with RXTE.
In \S 3 we outline the main features of the
diffusion model and related formulas. In \S 4 we show how the model integrated power vs
the driving oscillation frequency
 fits X-ray data from Cyg X-1.  In \S 5 we present the inferred correlation of the Reynolds  number
with   the driving oscillation frequency
and the spectral state (photon index). Application of the paper results to the observed index-QPO frequency correlations is considered in \S 6.
Discussion and final conclusions follow in \S 7.

\section{Observations}

For our analysis we used Cyg X-1   data from the Proportional Counter Array (PCA) and
All-Sky  Monitor (ASM) onboard {\it RXTE} [\citet{swank}].
The data are available through
the GSFC public archive \footnote{http://heasarc.gsfc.nasa.gov}. In this Paper we
present the analysis of a representative subset of {\it RXTE} observations of Cyg X-1.
 A reader can find the details of data reduction and analysis
 in \citet{st06} and TSA07. We chose approximately 200 observations to cover the
complete dynamical range of the source evolution from low/hard to high/soft state.
For the presented analysis we refit PDSs with our new model and we used the
results of our previous spectral analysis for photon index $\Gamma$.

To fit a PDS we used a sum of our perturbation diffusion model and one or two
Lorentzians to  account for the Low Frequency Quasi-Periodic Oscillations (LFQPOs).
For higher photon inicies, when the source is close to high/soft state,
the contribution of the accretion disk variability component sometimes becomes
significant. It is observed as an additional power law at the lower frequencies (see TSA07 for details).
We fit this component with simple power law, when it is needed.

\section{The main features of the model and underlying assumptions}
We consider  a scenario related to our model (see also TSA07) where
the Compton Cloud ( ``disk-like'' configuration) is located in the innermost part of the source  and the  Keplerian disk is extended from  the Compton Cloud (CC) to the optical companion
[see Fig. 1 in \cite{tf04}, hereafter TF04,  for the model geometry).

We remind the reader that the diffusion equation for the surface density  perturbation is the same
for any ``disk-like'' configuration for which   the rotational frequency $\Omega(R)$ as a function of radius $R$ has a Keplerian-like profile namely $\Omega\propto R^{-3/2}$ [see \cite{wo01} for details].
The standard Keplerian disk  and  ADAF kind of flow (Compton Corona) are particular examples of these accretion ``disk-like''' configurations.

  The CC  presumably contracts when the source goes to the softer state.  TF04  infer  that
the CC cloud in low/hard state is about 40 Schzwarzchild radii ($R_{\rm S}$)  whereas that in high/soft state is about 4-5 $R_{\rm S}$.
It is obvious that the variability of the  mass accretion rate in  the cloud leads  to the variability of  the gravitational energy release there.

The Earth observer sees this  mass accretion rate ($\dot M$) variation  as a variability of X-ray flux coming from the source given that   $\dot M$ regulates the supply of the soft seed photons up-scattered off CC hot electrons.   According to our scenario  in  the equatorial plane the plasma is  more dense and consequently colder than that in the CC outer parts.  The soft photons are produced in these relatively cold equatorial layers of CC   and then they are Comptonized off hot electrons of the CC outer part  forming the resulting  X-ray spectrum.

Thus  one can conclude that the variability of X-ray signal at energies higher than 3 keV (RXTE energy range)   is mostly  determined by   the  fluctuations of the  luminosity $\Delta L_x(t)$  originated  in the CC.  Here we study   the luminosity fluctuations $\Delta L_x(t)$  in the CC configuration.

 We assume that  the mass accretion rate variations $\Delta \dot M(0,t)$ is converted with efficiency $\varepsilon_{eff}$ into
the variations of the X-ray luminosity, i.e. $\Delta L_x(t)= \varepsilon_{eff}\Delta \dot M(0,t)$.
TSA07 show that the  fluctuations of
the resulting X-ray oscillation signal $\Delta L_x(t)$ due to the diffusion of the driving perturbations is
 \begin{equation}
\Delta L_x(t)=\int_0^t \varphi(t^{\prime}) Y(t-t^{\prime})dt^{\prime},
\label{convdL}
\end{equation}
i.e. a convolution of the Green's function of the bounded configuration $Y(t)$ (WRN) and
the source variability function $\varphi(t)$.
The resulting power spectrum is
\begin{equation}
||F_{x}(\omega)||^2=||F_{\varphi}(\omega)||^2||F_{Y}(\omega)||^2
\label{pwsp_varphi_res}
\end{equation}
where $F_{x}(\omega),~F_{\varphi}(\omega),~F_{Y}(\omega)$ are  Fourier transforms of
$\Delta L_x(t), ~\varphi(t),~Y(t)$ respectively.
The WRN PDS  $||F_{Y}(\omega)||^2$   is described  by Eq. (64) in TSA07  (also see the asymptotic forms of that  in Eqs. 65-66  there).

 Using the  total power of the driving oscillations $P_{dr}$

 one can  present   the driving oscillation PDS as (see Eqs. 22 and B5 in TSA07)
 \begin{equation}
||F_{\varphi}(\nu)||_{\nu}^2=\frac{\hat\Gamma_{dr}  P_{dr}/(a{\pi})}{(\nu-\nu_{dr})^2 + (\hat\Gamma_{dr}/2)^{2}}
 \label{driv_norm}
 \end{equation}
where $\nu_{dr}=\omega_{dr}/(2\pi)$ is the driving oscillation frequency,  $\hat \Gamma_{dr}$ is a full width of half maximum (FWHM) of the
Lorentzian and a constant $a$ varies in the range between
$1$ and $2$ depending on the ratio of $2\nu_{dr}/\hat\Gamma_{dr}$:
\begin{equation}
a=1+\frac{2\arctan(2\nu_{dr}/\hat\Gamma_{dr})}{\pi}.
\label{par_a}
\end{equation}
 For example $a=1$ and $a=2$ when
$2\nu_{dr}/\hat\Gamma_{dr}\ll 1$ and $2\nu_{dr}/\hat\Gamma_{dr}\gg1$ respectively.

It is worth noting that Eqs (\ref{convdL}-\ref{par_a}) have been derived in TSA07 with an assumption that
 the local  driving perturbations $\Phi(t,\xi)$  are  damped quasiperiodic oscillations, namely
\begin{equation}
\Phi(t,\xi)=A_{\Phi}f(\xi)\exp(-\frac{1}{2}\Gamma_{dr} t+i\omega_{dr}t)
\label{driving_fourier}
\end{equation}
where the amplitude of the driving oscillation is function of $R$ only ($\xi=R^{1/2}$).
Note the damping coefficients $\hat\Gamma$  in Eq. (\ref{driv_norm}) and $\Gamma$   in Eq. (\ref{driving_fourier})  are related as $\Gamma =2\pi\hat\Gamma$.

Then TSA07  apply the mean-value theorem for the integral $W(R,t)$  of Eq. B2 in TSA07.
Namely the mean-value  theorem in its general form for the product of two continuos  functions $g(t)$ and $f(t)$ states that
if a  function $g(t)$ is positive, i.e. $g(t)>0$ then
$$
\int_a^bg(t)f(t)dt = f(x)\int_a^bg(t)dt
$$
where $a\leq x\leq b$.
Given that  the product of the Green's function $G(R,\xi, t)$ and the driving oscillation amplitude  $f(\xi)$ in Eq. B2 in TSA07 is positive
we obtain that
$$
W(R,t)=
A_{\Phi}\int_0^t dt^{\prime} \exp[-\Gamma_{dr}t^{\prime}/2+i\omega_{dr }(\xi_*)t^{\prime}] \int_{R_{in}}^{R_0}G(R,\xi, t-t^{\prime}) f(\xi)d\xi
$$
where $R_{in}\leq\xi_{\ast}\leq R_0$. Then TSA07  proceed  with the Fourier transformation and PDS determination of $W(R,t)$ and ultimately they derive equations (\ref{convdL}-\ref{par_a}).

In Fig. \ref{pds_model} we show a typical example of the model fit to the data using
Eq. (\ref{pwsp_varphi_res}). The parameters of PDS continuum for white-red noise component
(WRN) $||F_{Y}(\omega)||^2$ (see for details TSA07) are  the diffusion time scale $t_0$,  index  of the power-law
viscosity distribution $\psi$ and for the driving oscillation component $||F_{\varphi}(\omega)||^2$ they are
$\nu_{dr}$ and $\hat\Gamma_{dr}$
(see Eq. \ref{driv_norm}).

The power-law index of the viscosity distribution
$\psi$ is related to the power-law  index of the red noise in the WRN PDS (see TSA07):
$$
\alpha=\frac{3}{2}-\delta=\frac{16-5\psi}{2(4-\psi)} ~~~~ {\rm for~~~\psi>0}
$$
and
\begin{equation}
\alpha=2 ~~~~ {\rm for~~~\psi<0}.
\label{index_pds}
\end{equation}

The model predicted integrated power is (see TSA07)
\begin{equation}
P_{x,diff}\sim\frac{P_{dr}}{2\pi\nu_{dr}t_0({\cal Q}+1/4{\cal Q})DC}
\label{theory_obs_form}
\end{equation}
where ${\cal Q}=\hat\Gamma_{dr}/\nu_{dr}$ is a quality factor for the driving signal and $D$ is a factor of order of unity.
Equation  (\ref{theory_obs_form}) was derived use the mean value theorem for the integral of the product of two
functions. In TSA07 we assumed that  a constant $C$  related to  the mean value of
$||F_{\varphi}(\nu)||_{\nu}^2$  over the frequency integration range is about a few (see Appendix B2 in TSA07 for details).
Here we specify and obtain $C-$constant  when we compare the  model dependence $P_{x,diff}$ on $\nu_{dr}$ with the observable
$P_{x}$ on $\nu_{dr}$.  In order to make this comparison one should determine the best-fit parameter $t_0$ and $P_{dr}$ as
functions of
$\nu_{dr}$. Note that
to derive Eq. (\ref{theory_obs_form}) we also use  the fact that the  WRN PDS $||F_{Y}(\omega)||^2$  is
normalized to $1/(Dt_0)$ where $D\gax1$. (see Eq. B16 in TSA07).

Now we follow the method suggested in TSA07 to infer  $P_{dr}$ vs $\nu_{dr}$ from the observations.
Namely, given the fact that  the driving PDS is a constant at frequencies  $\nu\ll\nu_{dr}$  we have
 \begin{equation}
||F_{\varphi}(\nu)||_{\nu}^2=|| F_{\varphi}(0)||_{\nu}^2=\frac{\hat\Gamma_{dr}  P_{dr}/(a\pi)}{\nu_{dr}^2 + (\hat\Gamma_{dr}/2)^{2}}.
 \label{driv_norm0}
 \end{equation}
Because for any power spectrum $||F(\omega)||^2$
$$|| F(\omega)||^2d\omega=|| F(2\pi\nu)||^22\pi d\nu=||F(\nu)||_{\nu}^2d{\nu}$$
we obtain that (compare with Eq. \ref{pwsp_varphi_res})
\begin{equation}
|| F_x(\nu)||_{\nu}^2=(2\pi)^{-1} ||F_{\varphi}(\nu)||_{\nu}^2||F_{Y}(\nu)||_{\nu}^2.
 \label{Fnu_product}
 \end{equation}

Thus a combination of  Eqs. (\ref{driv_norm0}) and  (\ref{Fnu_product})
leads us to  determination of   the integrated power of the driving oscillations
 \begin{equation}
P_{dr} = \frac{a\pi(\nu_{dr}^2 + (\hat\Gamma_{dr}/2)^{2})}{\hat\Gamma_{dr} }||F_{\varphi}(0)||_{\nu}^2=
2\pi^2a \frac{\nu_{dr}^2 + (\hat\Gamma_{dr}/2)^{2}}{\hat\Gamma_{dr} }\frac{||F_{x}(0)||^2}{||F_{Y}(0))||^2}.
 \label{driv_norm1}
 \end{equation}
We remind a reader that the values of $\nu_{dr}$ and $\hat\Gamma_{dr}$ are the best-fit PDS parameters, $||F_{x}(0)||^2$ is the
observed PDS value at  $\nu=0$ and  $||F_{Y}(0))||^2$ is  a value of the normalized WRN PDS at $\nu=0$.  As we mention above  the integral of the normalized WRN PDS  $||F_{Y}(\nu))||^2$  over
$\nu$ is   $1/(Dt_0)$.

\section{The integrated power vs driving oscillation frequency and photon index}
In Figure \ref{nu_dr_vs_gamma} we present the observed correlation of low
frequency QPO centroid $\nu_{L}$ with the driving QPO frequency $\nu_{dr}$ (upper panel)
and photon index $\Gamma$ with $\nu_{dr}$ (lower panel).
These correlations imply  that   $\nu_{L}$ along with $\nu_{dr}$ increase when the source becomes softer.
In other words, the emission area [Compton cloud (CC)]  contracts when the source evolves to the soft states.

In Figure \ref{t0_vs_vdr} we also see this  effect of CC contraction as anticorrelation of the CC diffusion
time scale $t_0$ with  $\nu_{dr}$. The inferred dependence of $t_0$ vs $\nu_{dr}$ can be fitted
by the power law $t_0 \propto \nu_{dr}^{-2.13\pm0.14}$.

We  infer the integrated power of the driving oscillations $P_{dr}$  vs  $\nu_{dr}$
(see Eq. \ref{driv_norm1})
and then we obtain the  model integrated power  $P_{x, diff}$ vs $\nu_{dr}$  (see Eq. \ref{theory_obs_form}).
In Figure \ref{Pdr_vs_vdr}  we show that the dependence of $P_{dr}$ vs $\nu_{dr}$ can be  fitted by
power law $P_{dr} \propto \nu_{dr}^{-1.8\pm0.16} $.  Namely the driving oscillation power $P_{dr}$ decreases when the source (Cyg X-1)  goes to softer states.
Presumably the decay of $P_{dr}$ with
$\nu_{dr}$ is  also related to the  contraction of Compton cloud.
The driving oscillations can result from the Rayleigh-Taylor (RT) local instability [see e.g. \citet{c61} and  \citet{t03}] ].
The decay of $P_{dr}$  can be considered as a cumulative effect of the local Rayleigh-Taylor (RT)  instability
when  the effective area of a given configuration (CC)  undergoing  RT oscillations contracts.

In Figure \ref{p_x_vs_vdr} we present a comparison of the observable PDS integrated power
$P_{x}$  (black filled circle) with the model predicted $P_{x,diff}$ (crosses)
(see Eq. \ref{theory_obs_form}). One can see that the dependence $P_{x,diff}$ on  $\nu_{dr}$ is similar to the observable
correlation $P_{x}$ vs $\nu_{dr}$.

Note that we obtain the factor $C\sim 4$ (see Eq. \ref{theory_obs_form})
by shifting a set of the values of  $P_{x,diff}$  along  Y-axis to fall on top of $P_{x}$ values.
The power-law  $P_{x} \propto \nu_{dr}^{-0.48\pm 0.03}$ fits
 the dependence of the theoretical and observable integrated powers  vs the
driving oscillation frequency.

\section{The Reynolds number  of the accretion flow in Compton cloud configuration}

\cite{tlm98}, hereafter TLM98  introduced the Reynolds number
$\rm Re= V_{R}R/\hat\nu$  ($\gamma$ in their notation)  where $V_{R}$,  $\hat\nu$  are an average radial velocity,  an average  viscosity  over a given configuration respectively  and $R$ is a configuration scale.   They demonstrate that the size of the transition layer (CC)  between the fast rotating accretion disk and the relatively slow rotating central object (either BH or NS)  strongly depends on the Reynolds number $\rm Re$.  It is worth noting that  $\alpha-$viscosity parameter   introduced by \cite{ss73} is  related to the TL (CC)  parameter $\rm Re$.  Given that $\alpha\sim \hat \nu/(V_{s}H)$, where $V_s$ is the sound velocity in the ``disk-like'' configuration and $H$ is a half of the configuration vertical size, we obtain that
\begin{equation}
\rm Re\sim \lambda/\alpha.
\label{alpha_re}
\end{equation}
To infer this  formula one should  assume that $\lambda=H/R$ and $V_s\sim V_R$.

TSA07 has already shown that there is a possibility to infer $\rm Re$, and consequently $\alpha-$parameter
(see Eq. \ref{alpha_re}),  using the RXTE  observations of BHs and NSs.
This determination can be done  if   a particular RXTE  power spectrum (PDS) has   the white-red noise  (WRN)  component and also if the QPO low frequency $\nu_L$  is present there.  TSA07 argue that  the relation between observed frequencies $\nu_L$  and $1/t_0$ seen in Cyg X-1 PDSs is similar to the theoretical relation between  the diffusion frequency $\nu_{diff}$ and the frequency of CC volume (magneto-acoustic) oscillations $\nu_{MA}$ [see e.g. \cite{to99}].
This fact leads them to conclude that $\nu_L$ can be considered as the frequency of  the magneto-acoustic oscillations which theory was developed by \cite{tbw01}, hereafter TBW01.

Using the best-fit parameters of the PDSs we can even infer the evolution of
the Reynolds number of the accretion flow  in the Compton cloud (CC),  with the change of  photon index $\Gamma$.
In fact, TSA07  relate   diffusion time $t_0$  with ${\rm Re}$ and  a magneto-acoustic QPO frequency $\nu_{MA}$ as
\begin{equation}
t_0={4\over{3}}{4\over{(4-\psi)^2}}\left[{{V_{R}R_0}\over{\hat\nu(R_0)}}\right]\left(\frac{R_0}{V_{R}}\right)=
{4\over{3}}{4\over{(4-\psi)^2}}\frac{\rm Re}{a_{MA}\nu_{MA}},
\label{t0_mod}
\end{equation}
where $V_R\sim V_s$ and $a_{MA}$ is a numerical coefficient.

Formula (\ref{t0_mod}) leads to the equation
\begin{equation}
{\rm Re}=2\pi \left(\frac{a_{MA}}{2\pi}\right)\frac{3}{4}\frac{(4-\psi)^2}{4}(\nu_L t_0)
\label{Re}
\end{equation}
that allows us to infer a value of $\rm Re$ using the best-fit model parameters $t_0$ and the QPO low frequency  $\nu_L$
which is presumably close   to $\nu_{MA}$. Ultimately we can find the evolution of ${\rm Re}$ with the photon index $\Gamma$ given that  $\nu_L$,  $t_0$ and  the viscosity index $\psi$ evolve with $\Gamma$
 (see Figs. \ref{nu_dr_vs_gamma}-\ref{t0_vs_vdr} and \ref{psi_wrn}).

In Figure \ref{re_vs_alpha} we present the inferred  Reynolds number as a function of the photon index $\Gamma$.
We  use  Eq. (\ref{Re}) where we set $a_{MA}=2\pi$ (see details of this determination of $a_{AM}$  in TBW01 and TSA07) and the observable correlations of $\nu_L$ and $t_0$  with $\Gamma$ (see Figs. \ref{nu_dr_vs_gamma} and \ref{t0_vs_vdr}).   One can see that ${\rm Re}-$number
 steadily increases from 10 to  70 when the source evolves from low/hard state to high/soft state.
In contrast,  TSA07  found  that ${\rm Re} \sim 8\pm 2.5$. We note, however, that in TSA07 only WRN model was used
without accounting for driving oscillation distribution, which significantly affects the resulting value for $\psi$.
They also used a limited set of data.

Note the observed behavior of the Re-number  vs $\Gamma$ and mass accretion rate was
predicted by TLM98,
where  they  formulated a transition layer model
(TLM) and  studied its consequences for observations. It is important to emphasize that the ${\rm Re}-$number
along with the photon index $\Gamma$, the low frequency QPO $\nu_L$ and the driving frequency $\nu_{dr}$ can be
considered as characteristics  of the spectral state. All of them correlate with each other.

\section{Photon index-QPO frequency correlation}

TLM98 showed that the outer (adjustment) radius of the transition layer (CC) $R_{out}$ measured in the dimensionless
units  with respect to  Schwarzschild radius $R_{\rm S}=2GM/c^2$,
$r_{out}=R_{out}/R_{\rm S}$, anticorrelates with  ${\rm Re}-$number or photon index $\Gamma$  (spectral state) only.
Thus  $\nu_L$ (or $\nu_{MA}$) as a  ratio $\sim V_{MA}/R_{out}$ should correlate with $\Gamma$
(or ${\rm Re}-$number)
where values $\nu_L$  related to the same $\Gamma$  for different sources should be inversely proportional to a
mass of the central object (black hole or neutron star). Note that a plasma velocity $V_{MA}$  is also a function
of $\Gamma$  only.  The comparison of the observed  index--QPO frequency correlations for two
different sources (with two different masses) should lead to determination of their relative masses with respect each other.
This is the main idea behind  the method of weighing black holes (TLM98)  recently  applied for BH mass determination in
 a number of Galactic and extragalactic sources [see TF04; \citet{ft04}; \citet{dtg06};  \citet{str07} and \citet{st07}].

\section{Discussion and Conclusions}

 \cite{ct95} proposed  a model  of
the truncated Keplerian  disk  and hot corona located in the innermost part of the source using  arguments in terms of radiation hydrodynamics.
\cite{cgr99},  hereafter CGR99, were the first who supported   this model
using the specific form of the power spectra of X-ray radiation.
Particularly they noted that   two-component X-ray spectra (soft multicolour black-body and harder power law) are frequently observed from accreting black holes. These components are presumably associated with the different parts of the accretion flow (optically thick and optically thin respectively) in the vicinity of the compact source.
They also emphasized that for Cygnus X-1, the overall shape of the power density spectra  in the soft and hard spectral states can be  {\it qualitatively}  explained if the geometrically thin disc is sandwiched by the geometrically thick corona extending in a radial direction up to a large distance from the compact object. In the hard state the thin disc is truncated at some distance from the black hole followed by the geometrically thick flow. The break in the PDS is then associated with the characteristic frequencies in the accretion flow at the thin disc truncation radius.

However there is a difference between CGR99's suggestions and the results of our paper.
We come to the model of the truncated disk plus corona  using the fit of the theoretical model of the power spectrum (see TSA07) to the data. Whereas CGR99 proposed  a  {\it qualitative} explanation of the data using  Lyubarskii's idea on the formation of the power spectrum in X-ray binaries
[see L97].

Our results confirm the CGR99 conclusion that   a stable optically thick (but geometrically thin)  disk extends down to  small radii  (as indicated by the strong and stable soft component) and whereas prominent variations of the harder component (presumably related to Compton cloud) are present in the broad range  of time-scales (up to at least $10^2$  s;  see Figs. 2-3  in TSA07). We also   confirm   the observed  emergent
spectrum consisting of two components (soft stable component
due to the disc emission and harder highly variable component due to
Comptonization in the corona). The relative contribution of these
two components to the luminosity of an averaged spectrum would
then reflect the ratio of the energy releases in the disc and corona
(or mass accretion rates).  It is also worth noting that our presented analysis indicates  that the high-frequency part of the PDS (QPO and  turnover)  at about 10 Hz and  higher is possibly related  to the  local instabilities operating in the Comptonization region of the energy release
(see CGR99).
Note that \cite{gz05}  also pointed out the evolution of PDSs in XTE J15550-564 and XTE J1650-500. In particular  they showed a variable power in the Comptonized component  (the PDS high-frequency component) when  a given source evolves  from hard to soft states.

However there is a difference in details between the CGR99 and results of our papers (see also TSA07).
For example the break in the PDS  frequency range  between 0.01 and 1 Hz is associated with the  characteristic diffusion frequencies of the Compton cloud but not as that in CGR99 ``with the characteristic frequencies in the accretion flow at the thin disc truncation radius.''

\cite{abl05},  hereafter ABL05, suggested  a  model  of the PDS of Cyg X-1
which successfully presented a natural transition from hard
state through intermediate state to soft state and back, and also allowed them
to study the behavior of the Lorentzian components in detail. Using this  model
consisting of a power-law and two Lorentzian profiles,  ABL05 were
able to fit the Cyg X-1 PDSs, and to follow the components
from hard state through the transitions and back. By choosing
this  simple  empirical approach for the PDS data analysis ABS05 could
model the major features in all states with only three components.
The parameters used in ABL05 were the width  and peak frequency
 of the Lorentzians, along with the power at the peak frequency,
The parameter evolution and its correlation between each other can all be described
by continuous functions.

However ABL05 did not address to the nature  of the  components and  continuum of the power spectrum. Their PDS description was pure phenomenological (compare with that in TSA07 and this paper).

ABL05 also showed that the PDS
of Cyg X-1 is dominated by the same two Lorentzian components
at all times. They came  to this conclusion based  on the fact that
 the relation of the peak frequencies of these  Lorentzian components follows the pattern seen in both
other BH and NS systems, and  therefore  they proposed that the
physical processes responsible for them cannot be explained by
invoking magnetic fields, a solid surface, or an event horizon.

It is worth noting that we also find  that the diffusion (break) and QPO frequency follows the BH-NS pattern (see details in ST06 and TSA07).   In addition to this  we demonstrate  that  there is a certain correlation between QPO low frequency and driving (high) frequency and photon index (see Fig. 2)  and show a correlation between the diffusion time scale (an inverse of the diffusion frequency) and the driving frequency (see Fig. 3).  Furthermore   we  explain the nature of the observational appearances of the power and photon spectra evolution by  the evolution  of the truncated disk and  corona configurations when a X-ray source evolves from hard state to soft states.
 We come to the conclusion that the  truncated disk and  corona scenario should  be a common model in BH and NS systems.

In fact, TLM98   showed that the bounded configuration (Compton cloud) surrounding compact objects
is the transition layer (TL) that is formed as a result of dynamical adjustments of a Keplerian disk to the innermost sub- Keplerian boundary conditions. They argued that this type of adjustment is a generic feature of the Keplerian flow in the presence of the sub-Keplerian boundary conditions near the central object and that it does not necessarily require the presence or absence of a hard surface. TLM98 concluded that
an isothermal sub-Keplerian TL between the NS surface and its last Keplerian orbit forms as a result of this adjustment. The TL model is general and is applicable to both NS and BH systems.

As the conclusions we want to single out

1. That we explain the decay of the emergent time variability of X-ray emission in  compact  sources when these sources evolve from
low/hard   to high/soft states. We find that the resulting power $P_x$ from Cyg X-1  decays with the driving oscillation
frequency $\nu_{dr}$ as   $P_x\propto \nu_{dr}^{-0.5}$.

2. We show that the reciprocal  of the diffusion time scale of the perturbation $t_0^{-1}$,  the low frequency QPO $\nu_L$,
 the driving oscillation
frequency $\nu_{dr}$, inferred by fitting the  Cyg X-1 PDSs with our diffusion model, increase when the source
evolves from low/hard  state to  high/soft state.  This behavior of the PDS characteristics implies that the Compton cloud
contracts towards softer spectral states.
The  driving oscillations are  probably caused by  the local Rayleigh-Taylor  instability
which cumulative  $P_{dr}$ decreases when the effective area of the configuration producing the
RT oscillations  contracts. The decay in driving power leads to the decay in the total observed variability
power from the source.
Using  the fact that $t_0^{-1}$,  $\nu_L$, $\nu_{dr}$ increase with $\Gamma$ and $P_{dr}$, $P_x$ decrease with
$\Gamma$  we conclude, as a result of our  analysis, that  the Compton Corona shrinks
when Cyg X-1 goes from low/hard  state to high/soft state.

3. Our extensive data analysis of the power spectra from Cyg X-1 with an application of the method of
 ${\rm Re}-$number  determination developed in TSA07
 indicates  that ${\rm Re}$ related to Compton cloud configuration increases

 from values about  10 in low/hard state to that about  70  in high/soft state.
We confirm the predictions by TLM98 that ${\rm Re}-$number  should increase with index
and QPO frequencies.  Thus one can conclude that the observable index-QPO correlation is probably driven
by the increase of ${\rm Re}-$number   when the source evolves from low/hard state to high/soft state.
It is worth noting that inverse proportionality of the low-frequency QPO with respect   BH mass in the index-QPO
correlation leads to  the  method weighing BHs  employing  this index-QPO correlation.

We acknowledge very useful comments and suggestions by the referee.


\section{Introduction}

The need of resources is a main motivation behind distributed systems.
Take peer-to-peer (p2p) systems as an example. A p2p system is a distributed system that
has no centralized control.
The p2p systems have gained in popularity with the massive utilization of file-sharing
applications over the Internet, since 2000.  These systems propose a tremendous amount of
file resources.
More generally, there is an increasing amount of various computing devices
surrounding us:
IDC predicts that there will be 17 billions of traditional network devices
by 2012.
In such context, it is common knowledge that scalability has become one of
the most important challenges of today's distributed systems.

The scale-shift of distributed systems modifies the way computational entities communicate.
Energy dependence, disconnection, malfunctioning, and other environmental
factors affect the availability of various computational entities independently.
This translates into unregular periods of activity during which an entity
can receive messages or compute tasks.
As a result of this independent and periodic behaviors, these systems are inherently highly dynamic.

Quorum system is a largely adopted solution for communication in message-passing system.
Despite the interest for emulating shared-memory in dynamic systems~\cite{Her87,RAMBO,FRT05,CGGMS05},
there is no scalable solution due to the cost of their failure handling mechanism
or their operation complexity.
This paper proposes a new quorum system, Timed Quorum System (TQS), whose quorums
have a bounded lifetime and that intersect with high probability during their lifetime.
We propose an implementation of TQS that emulates a probabilistic
atomic memory, provided that each node is able to approximate the system size.
We show that the resulting quorum size is $O(\sqrt{nD})$. Factor $n$ is the number of nodes and
factor $D$ is required to handle the dynamism of nodes in the system and can
be bounded if operations are sufficiently frequent.
That is, quorum size becomes $O(\sqrt{n})$, which is optimal, as proved in~\cite{MRWW01},
for static settings.
Moreover, the expected time for an operation to contact a quorum is
$O(\log{\sqrt{nD}})$ message delays.

\paragraph{Related Work.}

Dynamic quorum system is an active research topic.
Some dynamic quorums rely on failure detectors where if a failure is detected,
then the quorum is adapted. This adaption leads to a redefinition of the
quorums~\cite{Her87,NW98} or to the replacement of the failed nodes in the
quorums~\cite{NN05,AM05,GAV07}. For example, in~\cite{AM05}, a communication
structure is continuously maintained to ensure that quorum intersects at all time
(with high probability).

Other solutions relies on periodic reconfigurations~\cite{RAMBO,CGGMS05} where
the quorum systems are subsequently replaced.  These solutions are different from
the previous ones since the newly installed quorums do not need to intersect with
the previous ones.
In~\cite{FRT05} a quorum abstraction states requires two
properties: (i)~intersection and (ii)~progress, in which the notion of time is
introduced.  First, a quorum of a certain type intersects the quorum of another
type contacted subsequently.  Second, each node of a quorum remains active
between the time the quorum starts being probed and the time the quorum stopped
being probed.

As far as we know TQS is the first quorum system that expresses guarantees that
are both timely and probabilistic.  Time and probability relax the
traditional intersection requirement of quorums.
We present a scalable emulation of a probabilistic atomic memory where each
operation is atomic with high probability and where expected operation message complexity is
$O(\sqrt{nD})$ and expected operation time complexity is $O(\log{\sqrt{nD}})$.
If operations are sufficiently frequent then $D$ becomes a constant leading to
quorum of size $O(\sqrt{n})$.

\section{System Model and Problem Definition}

\subsection{Model}

The computation model is very simple.
The system consists of $n$ nodes. It is dynamic in the following sense.
Every time unit, $cn$  nodes leave the system and $cn$
nodes enter the system, where $c$ is an upper bound on the percentage of
nodes that enter/leave the system per time unit and is called the \emph{churn}; this  can be seen as  new
nodes ``replacing'' leaving nodes.
A node leaves the system either voluntarily or because it crashes.
A node that leaves the system does not reenter it later.  (Practically,
this means that, when a node reenters the system, it
is considered as a new node; all its previous knowledge of the system
state is lost.)
For the sake of simplicity, it is assumed that for any subset $S$ of nodes, the
portion of replaced nodes is $c|S|$.
As explained below, the model can be made more complex.
The \emph{universe} $U$ denotes all the nodes of the system, plus the ones that
have already leave the system and the ones that have not joined the system yet.

\subsection{Problem}
Most of the dynamic models assume that dynamic events are dependent from each other: only a
limited number of nodes leave and join the system during a bounded period of time.
For instance in~\cite{CGGMS05}, it is assumed that nodes departures are dependent:
quorum replication ensures that all nodes of at least any two quorums remain active between two
reconfigurations occur.
However, in a real dynamic system, nodes act independently.
Due to this independence, even with a precise knowledge of the past dynamic events,
one can not predict the future behavior of a node.
That is, putting this observation into the quorums context, it translates into the impossibility
of predicting deterministically whether quorums intersect.

In contrast, TQS requires that quorums intersect with high probability.
This allows to use a more realistic model in which there is a certain probability
that nodes leave/join the system at the same time.
That is, the goal here is to measure the probability that quorum intersect while
time elapses.  Observe that, realistically, the probability that $k$ nodes leave the system
increases at the time elapses.  As a result, the probability that a
quorum $Q(t)$ probed at time $t$ and that a quorum $Q(t')$ probed at time $t'$
intersect decreases as the period $|t'-t|$ increases.
In the following we propose an implementation of TQS where
probability of intersection remains high.

More precisely, each quorum of our TQS implementation
is defined for a given time $t$.
Each quorum $Q(t)$ has a lifetime $\Delta$ that represents a period during which
the quorum is \emph{reachable}.  Differently to availability defined in~\cite{NW98},
reachability does not depend on the number of nodes that are failed in a quorum system
because this number is unpredictable in dynamic systems.
Instead, a $Q(t)$ quorum is reachable if at least one node of quorum $Q(t)$
is reached with high probability: if two quorums are reachable at the same
time, they intersect with high probability.
More generally, let two quorums $Q(t)$ and $Q(t')$ of a TQS be reachable during
$\Delta$ time (their lifetime is $\Delta$); if $|t-t'|\leq\Delta$ then  $Q(t)$ and
$Q(t')$ intersect with high probability.

\paragraph{Probabilistic Atomic Object.}
Initially, any object has a default value $v_0$ that is replicated at a set of nodes and $V$ denotes the set of
all possible values present in the system.  An object is accessed by read or write
operations initiated by some nodes $i$ at time $t\in T$ that returns or modify the object value $v$. ($T$ is the set
of all possible time instants.)  If a
node initiates an operation, then it is referred to as a \emph{client}.
All nodes of the system, including nodes of the quorum system, can initiate a read or a write
operation, i.e., all nodes are potential clients and the multi-reader/multi-writer
model is used.  In the following we only consider a single object accessed by operations that
must satisfy probabilistic atomicity.

A probabilistic atomic object aims at emulating a memory
that offers high quality of service despite
large scale and dynamism.
For the sake of tolerating scale-shift and dynamism, we aim at relaxing
some properties.  However, our goal is to provide each client with a
distributed shared memory emulation that offers satisfying quality
of service.
Quality of service must be formally stated by a consistency criterion that
defines the guarantees the application can expect from the memory emulation.  We
aim at providing quality of service in terms of accuracy of
read and write operations.  In other words, our goal is to provide the clients with
a memory that guarantees that each read or write operation will be successfully
executed with high probability.
We define the probabilistic atomic object as an atomic object
where operation accuracy is ensured with high probability.

Let us first recall properties 2 and 4 of atomicity from Theorem 13.16 of~\cite{Lyn96} which
require that any sequence of invocations responses of read and write operations applied to $x$
satisfies a partial ordering $\prec$ such that:

\begin{itemize}
\item $(\pi_1,\pi_2)$-\textit{ordering}: if the response event of operation $\pi_1$ precedes the
    invocation event of operation $\pi_2$, then it is not possible
    to have $\pi_2 \prec \pi_1$;
\item $(\pi_1,\pi_2)$-\textit{return}: the value returned by a read operation $\pi_2$ is the value
    written by the last preceding write operation $\pi_1$ regarding to $\prec$
    (in case no such write operation $\pi_1$ exists, this value returned is the
    default value).
\end{itemize}
The definition of probabilistic atomicity is similar to the definition of atomicity:
only Properties 2 and 4 are slightly modified, as indicated below.

\begin{definition}[Probabilistic Atomic Object]\label{def:patomicity}
Let $x$ be a read/write probabilistic atomic object.  Let $H$ be a complete sequence of invocations responses of read and write operations applied to object $x$.
The sequence $H$ satisfies probabilistic atomicity if and only if there is a partial ordering $\prec$ on the successful operations such that the following properties hold:
\begin{enumerate}
\item For any operation $\pi_2$, there are only finitely many operations $\pi_1$, such that $\pi_1\prec \pi_2$.
  \item Let $\pi_1$ be a successful operation. Any operation $\pi_2$ satisfies $(\pi_1,\pi_2)$-\textit{ordering} with high probability.
(If $\pi_2$ does not satisfy it, then $\pi_2$ is considered as unsuccessful.)
  \item if $\pi_1$ is a write operation and  $\pi_2$ is any
    operation, then either $\pi_2 \prec \pi_1$ or $\pi_1 \prec \pi_2$;
  \item Let $\pi_1$ be a successful operation. Any operation $\pi_2$ satisfies $(\pi_1,\pi_2)$-\textit{return} with high probability.
(If $\pi_2$ does not satisfy it, then $\pi_2$ is considered as unsuccessful.)
\end{enumerate}
\end{definition}

Observe that the partial ordering is defined on successful operations.  That is,
either an operation $\pi$ fails and this operation is considered as unordered or the operation succeeds and is ordered
with respect to other successful operations.

Even though an operation succeeds with high probability, in an infinite execution it is very
likely that at least one operation fails.  However, our goal is to provide the operation
requester (client) with high guarantee of success for each of its operation request.

\paragraph{Additional Notations and Definitions.}

This paragraph defines several terms that are used in the algorithm description.
First, recall that a shared object is accessed through read operations, which return
the current value of the object, and write operations, which modify the current value
of the object.  To clarify the notion of currency when concurrency happens, it is
important to explain what are the up-to-date values that could be considered as current.
We refer to the \emph{last value} as the value associated with the largest $\ms{tag}$
among all values whose propagation is complete.
We refer to the \emph{up-to-date values} at time $t$ as all values $v$ that satisfies
one of the following properties: \textit{(i)}~value $v$ is the last value or
\textit{(ii)}~value $v$ is a value whose propagation is ongoing and whose associated tag
is at least equal or larger to the tag associated with the last value.

\section{Timed Quorum System}

This section defines Timed Quorum Systems (TQS).
Before being created of after its lifetime elapses, a quorum is not
guaranteed to intersect with any other quorums, however, during
its lifetime a quorum is considered as available: two quorums that
are available at the same time intersect with high probability.
In dynamic systems nodes may leave at any time, but this probability
is bounded, thus it is possible to determine the intersection
probability of two quorums.

\paragraph{Definition of Timed Quorum System (TQS).}

Next, we formally define TQS that are especially suited for dynamic systems.
Recall that the universe $U$ contains the set of all possible nodes, including the one that have not
join the system yet.
First, we restate the definition of a \emph{set system} as a set of subsets of a universe of nodes.

\begin{definition}[Set System]\label{def:setsystem}
  A \emph{set system} ${\cal S}$ over a universe $U$ is a set of subsets of $U$.
\end{definition}

Then, we define the timed access strategy as an access strategy over a set system that may vary over time.
This definition is motivated by the fact that an access strategy defined over a set ${\cal S}$ can evolve.
To compare with the existing probabilistic dynamic quorums, in~\cite{AM05} the authors defined a dynamic quorum system using an evolving
strategy that might replace some nodes of a quorum while its access strategy remains identical
despite this evolution.  Unlike the dynamic quorum approach, we need a more general framework to
consider quorums that are different not only because of their structure but also because of how likely
they can be accessed.
The timely access strategy
adds a time parameter to the seminal definition access strategy given by Malkhi et al.~\cite{MRWW01},
A timely access strategy is allowed to evolve over time.

\begin{definition}[Timed Access Strategy]
A \emph{timed access strategy} $\omega(t)$ for a set system ${\cal S}$ at time $t\in T$ is a
probability distribution on the elements of ${\cal S}$ at time $t$.  That is,
$\omega : {\cal S} \times T \rightarrow [0,1]$ satisfies at any time $t\in T$:
$\sum_{s\in{\cal S}}\omega(s,t) = 1$.
\end{definition}

Informally, at two distinct instants $t_1 \in T$ and $t_2 \in T$, an access strategy might be different
for any reason. For instance, consider that some node $i$ is active at time $t_1$ while the same node $i$ is failed at time
$t_2$, hence it is likely that if $i\in s$, then $\omega(s,t_1) \neq 0$ while
$\omega(s,t_2) = 0$.  This is due to the fact that a node is reachable only when it is active.

\begin{definition}[$\Delta$-Timed Quorum System]\label{def:timedqs}
  Let ${\cal Q}$ be a set system, let $\omega(t)$ be a timed access strategy for ${\cal Q}$ at time $t$,
  and let $0 < \epsilon < 1$ be given.

  The tuple $\tup{{\cal Q}, \omega(t)}$ is a \emph{$\Delta$-timed quorum system} if for any
quorums $Q(t_1) \in {\cal Q}$ accessed with strategy $\omega(t_1)$ and $Q(t_2) \in {\cal Q}$
accessed with strategy $\omega(t_2)$,
we have:
\begin{eqnarray}
\Delta \geq |t_1 - t_2| &\Rightarrow& \Pr[Q(t_1) \cap Q(t_2) \neq \emptyset] \geq 1 - \epsilon. \notag
\end{eqnarray}
\end{definition}

\section{Timed Quorum System Implementation for Probabilistic Atomic Memory}

In the following, we present a completely structureless memory.
The quorum systems this memory uses does not rely on any structure which
makes it flexible.  In contrast with using a logical structured overlay (e.g.,~\cite{MKKB01}) for
communication among quorum system nodes, we use an unstructured communication overlay~\cite{GKM03}.
The lack of structure presents several benefits.  First, there is no need
to readapt the structure at each dynamic event. Second, there is no need for
detecting failure.
Our solution proposes a periodic replication.
To ensure
the persistence of an object value despite unbounded
leaves, the value must be replicated an unbounded number of times.
The solution we propose requires periodic operations and an
approximation of the system size.  Although we do not focus
on the problem of approximating the system size $n$, we suggest
the use of existing protocols approximating closely the system size
in dynamic systems~\cite{LKM06}.

\paragraph{Replicating during client operations.}

Benefiting from the natural primitive of the distributed
shared memory, values are replicated using operations.
Any operation has at its heart a quorum-probe that replicates value.
On the one hand, it is natural to think of a write operation as an
operation that replicates a value. On the other hand, in~\cite{AW98} a
Theorem shows that "read must write", meaning that a read operation
must replicates the value it returns.
This raises the question: if operations replicate, why does a memory
need additional replication mechanism?
In large-scale systems, it is also reasonable to assume that shared
objects are frequently accessed because of the large number of participants.

\paragraph{Quorum Probe.}

The algorithm is divided in three distinct parts that represent the state of the algorithm (Lines~\ref{line:state-start}--\ref{line:state-end}), the actions initiated by a client (Lines~\ref{line:active-start}--\ref{line:active-end}), and the actions taken upon reception
of messages by a node (Lines~\ref{line:passive-start}--\ref{line:passive-end}), respectively.
Each node $i$ has its own copy of the object called its value $\ms{val}_i$
and an associated tag $\ms{tag}_i$. Field $\ms{tag}$ is a couple of a counter
and a node identifier and represents, at any time, the version number of
its corresponding value $\ms{val}$.  We assume that, initially, there are $q$ nodes that own the default
value of the object, the other nodes have their values $\ms{val}$ set to $\bot$ and
all their $\ms{tag}$s are set to $\tup{0,0}$.

\input{alg/disseminate.tex}

Each read and write operation is executed by client $i$ in two subsequent phases, each
disseminating a message to $q = O(\sqrt{nD})$ nodes, where $D=1/(1-c)^{\Delta}$ is required
to handle churn $c$ during period $\Delta$.\footnote{In~\cite{MRWW01}, it has
been showed that $q = O(\sqrt{n})$ is sufficient in static systems.}
The two subsequent phases are called the \emph{consultation phase} and the \emph{propagation phase}.  The consultation
phase aims at consulting the up-to-date value of the object that is present
in the system. (This value is identifiable since it associates the
largest tag present in the system.)
More precisely, client $i$ disseminates a consultation message to $q$ nodes so that
each receiver $j$ responds with a message containing value $\ms{val}_j$
and tag $\ms{tag}_j$ so that client $i$ can update $\ms{val}_i$ and $\ms{tag}_i$.
In fact, $i$ updates $\ms{val}_i$ and $\ms{tag}_i$ if and only if
the $\ms{tag}_i$ has either a smaller counter than $\ms{tag}_j$ or it has an equal
counter but a smaller identifiers $i<j$ (node identifiers are always distinct); in this case we say
$\ms{tag}_i < \ms{tag}_j$ for short (cf. Lines~\ref{line:comparison1} and \ref{line:comparison2}).
Ideally, at the end of the consultation phase
client $i$ has set its value $\ms{val}_i$ to the up-to-date value.
Read and write operations differ from the value and tag that are propagated by the client
$i$.  Specifically, in case of a read, client $i$ propagates the value and tag pair freshly consulted,
while in the case of write, client $i$ propagates the new value to write
with a strictly larger tag than the largest tag that $i$ has consulted so far.
The propagation phase propagates the corresponding value and tag by dissemination among nodes.

\input{alg/disseminate2.tex}

Next, we focus on the dissemination procedure that is at the heart of the
consultation and propagation phases.
There are two parameters, $\ell, k$, that define the way all consultation or propagation messages
are disseminated.  Parameter $\ell$ indicates the depth of the dissemination, it is used to set a
time-to-live field $\ms{ttl}$ that is decremented at each intermediary node that participates in
the dissemination; if $\ms{ttl}=0$, then dissemination is complete.
Parameter $k$ represents the number of neighbors that are contacted by each intermediary participating
node.  Together, parameters $\ell$ and $k$ define the number of nodes that are contacted during a
dissemination. This number is $\frac{k^{\ell+1}-1}{k-1}$ (Line~\ref{line:dissemiate-size}) and represents
the number of nodes in a balanced
tree of depth $\ell$ and degree $k+1$: each node having at most $k$ children.
(This value is provable by recurrence on the depth $\ell$ of the tree.)
Observe that $\ell$ and $k$ are chosen such that the number of nodes that are contacted
during a dissemination be larger than $q$ as written Line~\ref{line:dissemiate-size}.

There are three kind of messages denoted by message $\ms{type}$: $\lit{CONS}$, $\lit{PROP}$,
$\lit{RESP}$ indicating if the message is a consultation message, a propagation message,
or a response to any of the two other messages.
When a new phase starts at client $i$, a time-to-live field $\ms{ttl}$ is set to $\ell$
and a sequence number $\ms{sn}$ is incremented.
This number is used in message exchanges to indicate whether a message corresponds to
the right phase.
Then the phase proceeds in sending continuously messages to $k$ neighbors waiting for their
answer (Lines~\ref{line:snd-nbrs-start1}--\ref{line:snd-nbrs-end1} and
Lines~\ref{line:snd-nbrs-start2}--\ref{line:snd-nbrs-end2}).
When the $k$ neighbors answer, client $i$ knows that the dissemination is ongoing.
Then client $i$ receives all messages until a large enough number $q$ of nodes
have responded in this phase, i.e., with the right sequence number (Lines~\ref{line:snd-quorum-end1}, \ref{line:snd-quorum-end2}).
If so, then the phase is complete.

Observe that during the dissemination, messages are simply marked (if not so), responded (to client $i$), and reforwarded
to other neighbors (until $\ms{ttl}$ is null).  Messages are marked by the node $i$ that participates into
a dissemination for preventing node $i$ from participating multiple times in the same dissemination (Line:~\ref{line:forward-start}).
As a result, if node $i$ is asked several times to participate, it first participates (Lines~\ref{line:participate-start}--\ref{line:participate-end}) and then it asks another node to participate
(Lines~\ref{line:forward-start}--\ref{line:forward-end-prob}).
More precisely, if $\ms{marked}[\ms{sn}]$ is true, then node $i$ re-forwards messages of sequence number $\ms{sn}$
without decrementing the $\ms{ttl}$.
Observe that phase termination and dissemination termination depends on the number of participants rather than the
number of responses:
it is important that enough participants participate in each dissemination for the phase to eventually
end.

\paragraph{Contacting Participants Randomly.}
In order to contact the participants randomly, we implemented a membership
protocol~\cite{GKM03}.  This protocol is based on Cyclon~\cite{VGS05}, thus, it
is lightweight and fault-tolerant.
Each node has a set of $m$ neighbors
called its view ${\cal N}_i$, it periodically updates its view and recomputes
its set of neighbors.
Our underlying membership algorithm provides each node with
a set of $m \geq k+1$ neighbors, so that phases of Algorithm~\ref{alg:gossip}
disseminate through a tree of degree $k+1$.
This algorithm shuffles the view at each cycle
of its execution so that it provides randomness in the choice of neighbors.
Moreover, it has been shown by simulation that the communication graph obtained
with Cyclon is similar to a random graph where neighbors are picked uniformly
among nodes~\cite{I05}.
Finally, for a different purpose we already have simulated this variant of Cyclon
in~\cite{FGJKR07}: the results obtained was really similar to the one obtained with artificial
uniformity.

For the sake of uniformity, the membership procedure
is similar to the Cyclon algorithm:
each node $i$ maintains a view ${\mathcal N_i}$ containing one
entry per neighbor.
The entry of a neighbor $j$ corresponds to a tuple containing
the neighbor identifier and its age.
Node $i$ copies its view, selects the
oldest neighbor $j$ of its view, removes the entry $e_{j}$ of $j$ from the copy
of its
view, and finally sends the resulting copy to $j$.  When $j$ receives the
view, $j$ sends its own view back to $i$ discarding possible pointers to
$i$, and $i$ and $j$ update their view with the one they
receive by firstly keeping the entries they received.  The age of neighbor $j$ entry
denotes the time that elapsed since the last message from $j$ has been received; this is
used to remove failed neighbor from the list. This variant of Cyclon
exchanges all entries of the view at each step and uses two additional parameters.

\section{Correctness and Performance Results}

This Section gives the result of our algorithm.
We assume that, initially, at least $q$ nodes own the default value
of the object. Assume also that at least one propagation phase from a successful operation starts
every $\Delta$ time units and let the time of any phase be bounded by $\delta$ time units.
Next, we assume that
our underlying communication protocol
provides each node with a view that represents a set of neighbors uniformly drawn at random among the
set of all active nodes.  Recall that Cyclon shuffles node views and provides communication graph
similar to a random graph~\cite{I05}.

The first Theorem shows that the proposed solution implements a TQS.
The second Theorem shows that our solution satisfies probabilistic atomicity.
By lack of space, the proofs are given in the Appendix.

\begin{theorem}
Algorithm~\ref{alg:gossip} implements a $\Delta$-Timed Quorum System, where $\Delta$ is the maximum time between
two subsequent propagation starts.
\end{theorem}

\begin{theorem}
Algorithm~\ref{alg:gossip} implements a probabilistic atomic object.
\end{theorem}

Next Lemmas show the performance of our solution:
the first Lemma gives the message complexity of our solution while the second Lemma gives
the time complexity of our solution.
Observe first that operations complete
provided that sent messages are reliably delivered.  Building onto this assumption,
an operation complete after contacting $O(\sqrt{nD})$ nodes.  The following Lemma
shows this result.

\begin{lemma}
If messages are not lost, an operation complete after having contacted $O(\sqrt{nD})$ nodes.
\end{lemma}
\begin{proof}
This is straightforward from the fact that termination of the dissemination process
is conditioned to the number of distinct nodes contacted: $q = O(\sqrt{nD})$, with $D = (1-c)^{-\Delta}$
(cf. Line~\ref{line:qsize}).
Since there are two disseminating phases in each operation, an operation is executed after
contacting $O(\sqrt{nD})$ nodes.
\end{proof}

Next Lemma indicates that an operation terminates in $O(\log{\sqrt{nD}})$ message delays, in expectation.

\begin{lemma}
If messages are not lost, the expected time of an operation is $O(\log{\sqrt{nD}})$ message delays.
\end{lemma}
\begin{proof}
The proof relies on the fact that $q'$ nodes are contacted uniformly at
random with replacement. In expectation, the number $q'$ that must be contacted to obtain $q$
distinct nodes is $q' = q = O(\sqrt{nD})$. Since nodes are contacted in parallel along a tree
of depth $\ell$ and degree $k+1$, the time required to contact all the nodes on the tree
is $\ell = O(\log_k{q})$.  That is, it is done in $\ell = O(\log_k{\sqrt{nD}})$
message delays.
\end{proof}

\section{Conclusion}

This paper addressed the problem of emulating a distributed shared memory that
tolerates scalability and dynamism while being efficient.
TQS ensures probabilistic intersection of quorums in a timely fashion.
Interestingly, we showed that some TQS implementation verifies a consistency
criterion weaker but similar to atomicity: probabilistic atomicity.  Hence,
any operation provided by some TQS satisfies the ordering required
for atomicity with high probability.
The given implementation of TQS verifies probabilistic atomicity, provides
lightweight ($O(\sqrt{nD})$ messages) and fast ($O(\log{\sqrt{nD}})$ message delays)
operations, and does not require reconfiguration mechanism since
periodic replication is piggybacked into operations.

Since we started tackling the problem that node can fail independently,
we are now able to implement probabilistic memory into more realistic models.
Previous solutions required that a very few amount of nodes could fail
at the same time.  More realistically, a model should allow node to act independently
while requiring that failures occurring at the same time are unlikely.
An interesting question is: what probabilistic consistency can TQS achieve
in such a realistic model? \\

\noindent {\bf Acknowledgments.}
We are grateful to Anne-Marie Kermarrec and Achour Most\'efaoui for
fruitful discussions about gossip-based algorithms and dynamic systems.

\bibliographystyle{splncs}


\section{Introduction}
\label{intro}

CODEX (= COsmic Dynamics EXperiment) is a concept for an extremely
stable, high-resolution optical spectrograph for the European
Extremely Large Telescope (E-ELT). The science case for CODEX
encompasses a large range of topics, including the search for
exo-planets down to earth-like masses, primordial nucleosynthesis and
the possible variation of fundamental constants. However, its prime
science driver is the exploration of the universal expansion history
by detecting and measuring the cosmological redshift drift using QSO
absorption lines. This is also one of the 9 `prominent' science cases
chosen by the E-ELT Science Working Group to be among the highlights
of the entire E-ELT science case. A description of the CODEX project
as a whole was given by \cite{Pasquini05}.

The recognition that an ultra-stable, high-efficiency, high-resolution
optical spectrograph would not only be an extremely valuable
instrument for the E-ELT but also for the VLT led to the development
of the ESPRESSO concept (= Echelle Spectrograph for PREcision Super
Stable Observations, see L.~Pasquini's contribution to these
proceedings). Again, there are a large number of applications for such
an instrument, as several other contributions to these proceedings
have highlighted. Hence, there is also a very strong science case for
ESPRESSO, including e.g.\ detailed studies of the intergalactic medium
and of stellar abundances.

However, apart from these scientific drivers, ESPRESSO will also
fulfil another role: CODEX will represent a major development in
high-resolution optical spectrographs compared to existing instruments
such as UVES and HARPS. In order to achieve its science goals CODEX
will have to deliver an exceptional radial velocity accuracy and
stability, i.e.\ $2$~cm~s$^{-1}$ over a timescale of $\sim 20$~yr.
Although the basic design concepts are already in place, several of
the sub-systems needed to achieve the CODEX requirements do not
currently exist. However, they will be implemented in ESPRESSO for the
first time. Hence, in many respects ESPRESSO will be a CODEX precursor
instrument that will allow us to test and gain experience with the
novel aspects of these instruments. Here we will discuss ESPRESSO in
the context of its CODEX precursor role, both in a technical sense as
well as with respect to the main CODEX science driver, which we
briefly describe next.

\section{Cosmic Dynamics}
The discovery from type Ia SNe that the universal Hubble expansion
appears to have begun accelerating at a relatively recent epoch, and
its profound implications for fundamental physics have sparked an
intense interest in the observational exploration of the Universe's
expansion history. Several methods for measuring the Hubble parameter
$H(z)$ already exist but all of them are either geometric in nature or
use the dynamics of localised density perturbations. The simplest,
cleanest and most direct method of determining the expansion history,
however, is to observe the dynamics of the global Robertson-Walker
metric itself. One way to achieve this is by measuring the so-called
redshift drift, i.e.\ the tiny, systematic drift as a function of time
in the redshifts of cosmologically distant sources (Fig.\
\ref{vdot}). This effect is directly caused by the de- or acceleration
of the universal expansion and can hence be used to determine its
history. A measurement of this effect would be able to provide
evidence of the acceleration that is entirely independent of the SNIa
results or any other cosmological observations, and that does not
require any cosmological or astrophysical assumptions at all. It would
also provide $H(z)$ measurements over a redshift range inaccessible by
other methods. Recently, \cite{Liske08} found that a $42$-m telescope
would indeed have the photon collecting power to detect the redshift
drift by monitoring the redshifts of QSO absorption lines over a
timescale of $\sim 20$ years (Fig.\ \ref{vdot}), providing a strong
motivation for a CODEX-like instrument at the E-ELT.

\begin{figure}
\centering
\includegraphics[height=8cm,angle=-90]{fig1.ps}
\caption{The solid lines show the redshift drift as a function of
  redshift in velocity units for two different combinations of
  $\Omega_{\rm M}$ and $\Omega_\Lambda$ as indicated, and a Hubble
  constant of $H_0 = 70$~km~s$^{-1}$~Mpc$^{-1}$. The grey shaded areas
  result from varying $H_0$ by $\pm 8$~km~s$^{-1}$~Mpc$^{-1}$. The
  three sets of `data' points show Monte Carlo simulations of a
  redshift drift experiment with CODEX/E-ELT using a total of
  $4000$~h observing time and a total experiment duration of
  $20$~yr. Each of the sets of points corresponds to a different
  implementation of the drift experiment pursuing different
  observational goals. See \cite{Liske08} for more details.}
\label{vdot}
\end{figure}

\section{ESPRESSO as a CODEX Pathfinder}
\subsection{Technical aspects}
The UVES and HARPS experiences have allowed us to identify a number of
properties that a spectrograph must feature in order to deliver
exceptional radial velocity accuracy and long-term stability,
including: simultaneous wavelength calibration, a fully passive
instrument with zero human access, located inside a vacuum tank which
is itself located inside a nested environment in an underground
facility that allows progressively more precise temperature and
pressure control, and the flux-weighted timing of observations with
sub-second precision. Temperature control of the CCD will be
particularly important, while high system throughput will also be of
the essence. Some of these concepts are already established. However,
two of the most critical aspects are also those requiring the most
R\&D: light scrambling and wavelength calibration.

At a resolution of $150\,000$ a typical pointing accuracy of $\sim
0.05$~arcsec corresponds to an error of $100$~m~s$^{-1}$ necessitating a
scrambling gain of $\sim 5000$ in order to reach $2$~cm~s$^{-1}$
accuracy. Hence, in addition to any fibre we will require a dedicated
scrambling device to ensure that a photon's position on the CCD only
depends on its wavelength but not on its position on the entrance
aperture.

Current wavelength calibration sources such as ThAr lamps and I$_2$
cells are sub-optimal in several respects, their non-uniformity and
lack of long-term stability being among the concerns. However, a new
concept for wavelength calibration has recently emerged. A `laser
frequency comb' system provides a series of uniformly spaced, very
narrow lines whose absolute positions are known a priori with a
relative precision of $\sim$$10^{-12}$ (see A.~Manescau's
contribution; \cite{Murphy07}).

Neither of the two systems above currently exist, but they would be
developed for ESPRESSO. Being able to test and validate them `on the
sky' would provide valuable experience and input for further
improvements.

\subsection{Scientific aspects}
The scientific goals of CODEX are sufficiently removed from current
observational reality to require validation and demonstration of
feasibility of all aspects of data handling and analysis. This
includes data acquisition strategies (e.g.\ minimum and maximum viable
exposure times), the tracking of CCD distortions, and the accuracy of
flat-fielding, sky subtraction and scattered light corrections.
The extraction of the cosmological signal from the data will also
require testing. Issues include how to deal with QSO variability and
the accuracy of the conversion to the cosmological reference frame. In
addition ESPRESSO will allow us to determine the currently unknown
intrinsic widths of the narrowest metal absorption lines in order to
reassess their usefulness for the drift experiment, and to look for
any sources of astrophysical noise so far overlooked.

Data on QSOs collected with ESPRESSO for other scientific purposes
would allow us to address all of the above issues. We estimate that
$\sim 200$ hours of observations of the brightest known QSOs would
provide an end-to-end system verification, from data acquisition to
signal extraction, at the level of $\sim 30$--$40$~cm~s$^{-1}$.

\begin{figure}
\centering
\includegraphics[height=8cm,angle=-90]{fig2.ps}
\caption{Expected constraints in the $\Omega_\Lambda$-$\Omega_{\rm M}$
  plane from the redshift drift experiment with CODEX/E-ELT described
  in detail in \cite{Liske08}. The coloured ellipses show the joint
  $68$ and $90$ per cent confidence regions that result from a total
  integration time of $4000$~h and a total experiment duration of
  $\Delta t = 20$~yr. The hashed region indicates the $95$ per cent
  lower limit on $\Omega_\Lambda$. The solid contour shows the
  improvement of the $68$ per cent confidence region that results from
  the additional investment of $4000$~h of observing time using
  ESPRESSO on the VLT in its `SuperHarps' mode (i.e.\ at $R \approx
  150\,000$ and using one UT), assuming that these observations take
  place $\sim 8$~yr before the start of the CODEX observations. The
  $95$ per cent lower limit on $\Omega_\Lambda$ of the combined
  experiment is shown has the horizontal line above the shaded
  region. Flat cosmologies and the boundary between current de- and
  acceleration are marked by solid black lines. The dark shaded region
  in the upper left corner designates the regime of `bouncing
  universe' cosmologies which have no big bang in the past.}
\label{ol_om}
\end{figure}

\section{CODEX + ESPRESSO = $\dot z$?}
Since ESPRESSO will have characteristics similar to those of CODEX the
question arises whether ESPRESSO can be used to make a start on the
redshift drift experiment. The idea is that since ESPRESSO would be
available several years before CODEX data appropriately collected with
ESPRESSO could serve as a `zeroth' epoch measurement, effectively
extending the time baseline of the experiment for a few years, thereby
improving the final result without delaying it. Fig.\ \ref{ol_om}
shows the comparison of the cosmological constraints in the
$\Omega_\Lambda$-$\Omega_{\rm M}$ plane expected from a drift
experiment using CODEX only (coloured ellipses) and CODEX + ESPRESSO
(solid contour), where we have assumed that ESPRESSO would take up
operation $8$ years before CODEX. Evidently the extension of the time
baseline by $8$ years is not enough to offset the lack of the VLT's
photon collecting power compared to the E-ELT: the improvement of the
constraints is only quite modest, with the lower limit on
$\Omega_\Lambda$ increasing by $\sim 20$ per cent.