\section{Introduction}

\subsection{Background and motivation}\label{sub-background}

Distributed systems composed of  limited agents that  interact in a stochastic
fashion to jointly perform tasks are common in the natural world as well as in
engineered  systems. Examples  include a wide range of insect populations
\cite{HM85}, chemical reaction networks \cite{CCDS14}, and
mobile~sensor~networks \cite{Pop1}. Such systems have been studied in various
disciplines, including biology, physics, computer science and chemistry, while
employing different mathematical and experimental tools. 

From an algorithmic perspective, such complex systems share a number of
computational challenges. Indeed, they  all perform collectively in
dynamically changing environments despite being composed of limited individuals
that communicate through seemingly unpredictable, unreliable, and  restricted
interactions. Recently, there has been significant interest in understanding
the  computational limitations that are inherent to such systems, by
abstracting some of their characteristics as distributed computing models, and
analyzing them algorithmically \cite{Dan2,Pop1,AFJ06,BCN15,Doty,OHK14}.
These models usually consider  agents which are restricted in their memory and
communication capacities, that interact independently and uniformly at random
(u.a.r.). By now, our understanding of the computational power of such models
is rather advanced. However, it is important to note that much of this
progress has been made assuming non-faulty scenarios - a rather strong
assumption when it comes to natural or sensor-based systems. 
For example, to synchronize actions between processors, many known distributed
protocols rely on the assumption that processors know when the protocol is
initiated. However, in systems composed of limited individuals that do not
share a common time notion, and must react to a  dynamically changing
environment, it is often unclear how to achieve such conditions. To have a
better  understanding of such systems, it is  desirable to identify the weakest
computational models that still allow for both efficient as well as robust
computations. 

This paper concentrates on the basic $\mathcal{PULL}$ model of communication
\cite{DGH88,DF11a,DGM11,KSSV00}, in which in each round, each agent can
extract (pull) information from few other agents, chosen u.a.r. In the computer
science discipline, this model, as well as its companion $\mathcal{PUSH}$ model, gained
their popularity due to their simplicity and  inherent robustness to different
kinds of faults. Here, focusing more on the context of natural systems, we view
the $\mathcal{PULL}$ model as an abstraction for communication in well-mixed scenarios,
where agents can occasionally ``observe'' arbitrary other agents.
We aim to identify the minimal model requirements with respect to
achieving basic information dissemination tasks under conditions of increased
uncertainty. 
As many natural systems appear to be more restricted by their communication
abilities than by their memory capacities \cite{Survey,beeping1,emek}, our main
focus is on understanding what can be computed  while revealing as few bits per
interaction as possible\footnote{We note that stochastic communication patterns
such as $\mathcal{PULL}$ or $\mathcal{PUSH}$ are  inherently sensitive to congestion issues.
Indeed, in such models it is unclear how to simulate a protocol that uses large
messages while using only small size messages. For example, the straightforward
strategy of breaking a large message into small pieces and sequentially sending
them one after another  does not work, since one typically cannot make sure
that the small messages reach the same destination. Hence, reducing the message
size  may have a profound impact on the running time, and perhaps even on the
solvability of the problem at hand.}.
\medskip

\paragraph{Self-stabilizing  Bit Dissemination\xspace.}

Disseminating information from one or several sources to the rest of the
population\xspace is one of the most fundamental building blocks in distributed
computing \cite{CHHKM12,CLP09,DGH88,DF11a,KSSV00}, and an important primitive
in natural systems \cite{FishConsensus,Razin,ManyEyes}. 
Here, we focus on the {\em Majority\xspace Bit Dissemination\xspace} problem defined as follows. We consider a population\xspace of $n$ agents.
The population\xspace may contain multiple {\em source agents} which are specified by
a designated bit in the state of an agent indicating whether the agent is a
source or not. 
Each source agent holds a binary {\em input bit\xspace}, however, sources may not
necessarily agree on their input bits\xspace. In addition, each agent holds a binary
{\em output bit} (also called {\em opinion\xspace}).
The goal of all agents is to converge their opinion\xspace on the majority bit
among the initial input bits\xspace of the sources, termed $b_{maj}$. This problem
aims to capture scenarios in which some individuals view themselves as
informed, but some of these agents could also be wrong, or not up-to-date. Such
situations are common in nature  \cite{COU05,Razin} as well as in man-made
systems. The number of sources is termed $k$. We do not assume that agents know
the value $k$, or that sources know whether they are in the majority or
minority (in terms of their input bit\xspace). For simplicity, to avoid dealing with
the case that the fraction of the majority input bit\xspace among sources is
arbitrarily close to that of  the minority input bit\xspace, we shall guarantee
convergence only when the fraction of source agents holding the majority
input bit\xspace is bounded away from $1/2$. 

The particular case where we are promised to have $k=1$ is called Bit Dissemination\xspace,
for short. In this case we have a single source agent that aims to disseminate
its input bit\xspace $b$ to the rest of the population\xspace, and there are no other
sources introducing a conflicting opinion. Note that this  problem has been
studied extensively in different models under different names (e.g., {\em
Broadcast} or {\em Rumor Spreading}). 
A classical example of Bit Dissemination\xspace considers the  synchronous $\mathcal{PUSH}$/$\mathcal{PULL}$
communication model, where $b$ can be propagated from the source  to all other
agents in $\mathcal O(\log n)$ rounds, by simply letting each uninformed agent copy
it whenever it sees an informed agent \cite{KSSV00}. The correctness of this
protocol heavily relies on the absence of incorrect information held by  agents. Such reliability however may be difficult to achieve in dynamic
or unreliable conditions. 
For example, if the source is sensitive to an unstable environment, it may
change its mind several times before stabilizing to its final opinion\xspace.
Meanwhile, it may have already invoked several consecutive executions of the
protocol with contradicting initial opinions\xspace, which may in turn ``infect''
other agents with the wrong opinion\xspace $1-b$. If agents do not share a common
time notion, it is unclear how to let infected agents distinguish their current
wrong opinion\xspace from the more ``fresh'', correct opinion\xspace.  
To address such difficulty, we consider the context of {\em
self-stabilization} \cite{dijkstra}, where agents must converge to a correct
configuration from any initial configuration of states.


\subsection{Technical difficulties and intuition}\label{sec:technical}



Consider the Bit Dissemination\xspace problem (where we are guaranteed to have a single source agent). This particular case is already difficult in the self-stabilizing context if we are restricted to use $O(1)$ bits per interaction. As hinted above, a main difficulty lies  in the fact that agents do not necessarily share a common time notion. Indeed, it is easy to see that if all agents share the same clock, then convergence can be achieved in $\mathcal O(\log n)$ time with high probability (w.h.p.), i.e, with a probability of at least $1 - n^{-\Omega(1)}$, and using two bits per interaction. 
\medskip

\paragraph{Self-stabilizing Bit Dissemination\xspace ($k=1$) with 2 bits per interaction, assuming synchronized clocks.}
The source sets her output bit to be her input bit $b$. In addition to communicate its output bit $b_u$, each agent $u$ stores and communicates a {\em certainty} bit~$c_u$. Informally, having a certainty bit equal to 1 indicates that the agent is certain of the correctness of its output bit. The source's certainty bit is always set to 1.  Whenever a non-source agent $v$ observes $u$ and sees the tuple $(b_u,c_u)$, where $c_u=1$,  it copies the output and certainty bits of $u$ ({\em i.e.,} sets $b_v=b_u$ and $c_v=1$). In addition,  all non-source agents count rounds, and reset their certainty bit to~0 simultaneously every $T=\mathcal O(\log n)$ rounds. The reset allows to get rid of ``old'' output bits
that may result from applying the protocol before the source's output bit has stabilized. This way, from the first time a reset is applied after the source's output bit has stabilized, the correct source's output bit will propagate to all agents within $T$ rounds, w.h.p. 
Note however, that if agents do not share a consistent notion of time they cannot  reset their certainty bit to zero simultaneously. In such cases, it is unclear how to prevent agents that have just reset their certainty bit to 0 from being ``infected'' by ``misleading'' agents, namely, those that have the wrong output bit and certainty bit equal to 1.
\medskip
\paragraph{Self-stabilizing Bit Dissemination\xspace ($k=1$) with a single bit per interaction, assuming synchronized clocks.}
Under the assumption that all agents share the same clock, the following trick shows how to obtain convergence  in $\mathcal O(\log n)$ time and using only a single bit per message, namely, the output bit. As before, the source sets her output bit to be her input bit $b$. Essentially, agents divide time into phases of some prescribed length $T=\mathcal O(\log n)$, each of them being further subdivided into $2$ subphases of length $T/2$. In the first subphase of each phase, non-source agents are {\em sensitive} to opinion\xspace $0$. This means that whenever they see a $0$ in the output bit of another agent, they turn their output bit to $0$, but if they see 1 they ignore it. Then, in the second subphase of each phase, they do the opposite, namely they switch their output bit to $1$ as soon as they see a $1$ (see Figure \ref{fig:wheel}). %
Consider the first phase starting after initialization.  If $b=0$ then within one complete subphase $[1,T/2]$, every output bit is $0$ w.h.p., and remains there forever. Otherwise, if $b=1$, when all agents go over a subphase $[T/2+1, T]$ all output bits are set to $1$ w.h.p., and remain $1$ forever. Note that a common time notion is required to achieve correctness.

\begin{figure}[!ht]
    \centering
    \includegraphics[width=0.34\textwidth]{pics/wheel.pdf}
    \caption{The division in subphases used for self-stabilizing Bit Dissemination\xspace with a clock. During the first half, between times $1$ and $T/2$, agents are sensitive to $0$. Then they are sensitive to $1$.} \label{fig:wheel}
\end{figure}
 
The previous protocol indicates that the self-stabilizing Bit Dissemination\xspace problem is highly related to the self-stabilizing {\em Clock Synchronization\xspace} problem, where each agent internally stores a clock\xspace modulo $T=\mathcal O(\log n)$  incremented at every round and,  despite having arbitrary initial states, all agents should converge on sharing the same value of the clock\xspace. Indeed, given such a protocol,  one can obtain a self-stabilizing Bit Dissemination\xspace protocol by running the Clock Synchronization protocol in parallel to the last example protocol. This parallel execution costs only an additional  bit to the message size and a $\mathcal O(\log n)$ additive factor to the time complexity over the   complexities of the Clock Synchronization protocol. 
\medskip


\paragraph{Intuition behind the self-stabilizing Clock Synchronization algorithm.}

Our technique for obtaining the Clock Synchronization protocol is based on a
compact recursive use of the stabilizing consensus protocol  proposed by Doerr
et al. \cite{DGM11} through our Message Reduction Theorem{} (Theorem \ref{lem:saving}). 

In the Preliminary section (Section \ref{sec:simple}) we describe a simple
protocol called \textsc{Syn-Simple}\xspace that uses $\mathcal O(\log T)$ bits per message. In \textsc{Syn-Simple}\xspace,
each agent $u$ maintains  a clock $C_u \in [0, T-1]$. At each round, each agent
$u$ displays the opinion\xspace of her clock, pulls~$2$ other such clock
opinions\xspace, and updates her clock as the bitwise majority of the two clocks
she pulled and her own. Then the clock $C_u$ is incremented.  This protocol
essentially amounts to running the protocol of Doerr et al. on each bit
separately and in parallel, and self-stabilizes in $\mathcal O(\log T \log n)$
rounds w.h.p. (Proposition \ref{prop:simple}).


We want to apply a strategy similar to \textsc{Syn-Simple}\xspace, while using only $\mathcal O(1)$
many bits per interaction.
The core technical ingredient, made rigorous in the \corelem\xspace, is that a certain
class of protocols using messages of $\ell$ bits, to which \textsc{Syn-Simple}\xspace belongs,
can be emulated by another protocol which uses $\lceil \log \ell \rceil +1$
bits only.
The idea is to build a clock\xspace modulo $\ell$ using \textsc{Syn-Simple}\xspace itself on
$\lceil \log \ell \rceil$ bits and sequentially display one bit of the
original $\ell$-bit message according to such clock. Thus, by applying such
strategy to \textsc{Syn-Simple}\xspace itself, we use a smaller clock\xspace modulo $\ell' \ll
\ell$ to synchronize a clock\xspace modulo $\ell$. Iterating such process,
in Section \ref{sub:powerof}, we obtain a compact protocol which uses only $3$
bits. 



\subsection{The model}
\label{sec:model}
\bigskip
\paragraph{The communication model.}  

We adopt the the synchronous $\mathcal{PULL}$ model \cite{BCN16,DGH88}. Specifically, in the $\mathcal{PULL}(\eta)$ model, communication proceeds in discrete rounds.
In each round, each agent $u$ ``observes'' $\eta$ arbitrary other agents, chosen u.a.r.%
\footnote{``u.a.r.'' stands for ``uniformly at random'', with replacement.}
among all agents, including herself.
(We often omit the parameter $\eta$ when it is equal to 2). 
When an agent $u$ ``observes'' another agent $v$, she can peek into a designated {\em visible part} of $v$'s memory. If several agents observe an agent $v$ at the same round then they all see the same visible part. The {\em message size} denotes the  number of bits stored in the visible part of an agent. We denote with $\mathcal{PULL}(\eta,\ell)$
the $\mathcal{PULL}(\eta)$ model with message size $\ell$. 
We are primarily interested in message size that is independent of $n$, the number of agents.
\medskip

\paragraph{Agents.} 
We assume that agents do not have unique identities, that is, the system is {\em anonymous}. We do not aim to minimize the (non-visible) memory requirement of the agent, yet, we note that our constructions can be implemented with relatively short memory, using $\mathcal O(\log\log n)$ bits. We assume that each agent internally stores a clock\xspace modulo some integer $T=\mathcal O(\log n)$, which is incremented at every round.
\medskip



\paragraph{Majority\xspace Bit Dissemination\xspace problem.}

We assume a system\xspace of $n$ agents each having an internal state that contains an {\em indicator bit} which indicates whether or not the agent is a {\em source}. Each source holds a binary {\em input bit\xspace}\footnote{
Note that having the indicator bit equal to 1 is equivalent to possessing an input bit: both are exclusive properties of source nodes. However, we keep them distinct for a clearer presentation.
}and each agent (including sources) holds a binary {\em opinion\xspace}. 
The number of sources (i.e., agents whose indicator bit is $1$) is denoted by $k$. We denote by $k_0$ and $k_1$ the number of sources whose input bit\xspace is initially set to  $1$ and $0$, respectively.
Assuming $k_1\neqk_0$, we define the \emph{majority bit}, termed $b_{maj}$, as $1$ if $k_1 >k_0$ and $0$ if $k_1<k_0$.
Source agents know that they are sources (using the indicator bit) but they do not know whether they hold the majority bit. The parameters $k$, $k_1$ or $k_0$ are not known to the sources or to any other agent.  
It is required that the opinions\xspace of all agents eventually converge to the majority bit%
$b_{maj}$. 
We note that agents hold their output and indicator bits privately, and we do not require them to necessarily reveal these bits publicly (in their visible parts) unless they wish to. 
To avoid dealing with the cases where the number of sources holding the majority bit is arbitrarily close to $\frac k2$, we shall guarantee correctness (w.h.p.)
only if the fraction of sources holding the majority is bounded away from~$\frac{1}{2}$, i.e., only if $|\frac{k_1}{k_0}-1|>\epsilon$, for some positive constant $\epsilon$.  
When $k=1$, the problem is called {\em Bit Dissemination\xspace}, for short. Note that in this  case, the single source agent holds the bit $b_{maj}$ to be disseminated and there is no other source agent introducing a conflicting opinion.
\medskip
 
\paragraph{$T$-Clock Synchronization\xspace.}

Let $T$ be an integer. In the {\em $T$-Clock Synchronization\xspace} problem, each agent maintains a {\em clock\xspace} modulo $T$ that is incremented at each round. The goal of agents is to converge on having the same value in their clocks\xspace modulo $T$. (We may omit the parameter $T$ when it is clear from the context.)
\medskip

\paragraph{Probabilistic self-stabilization and convergence.}

Self-stabilizing protocols are meant to guarantee that  the system\xspace eventually 
converges to a \emph{legal} configuration regardless of the initial states of the
agents \cite{dijkstra}. Here we use a slightly weaker notion, called {\em probabilistic self-stabilization}, where stability is guaranteed w.h.p. \cite{BCN15b}. More formally, for the  Clock Synchronization\xspace problem, we assume that {\em all} states are initially set by an adversary. For the  Majority\xspace
Bit Dissemination\xspace problem, we assume that {\em all} states are initially set by an adversary except that it is assumed 
that the agents know their total number $n$, and that this information is not corrupted. 


In the context of $T$-Clock Synchronization\xspace, a legal configuration is reached when all clocks show the same time modulo~$T$, and in the Majority\xspace Bit Dissemination\xspace problem, a legal configuration is reached when all agents output  the  majority bit $b_{maj}$.
Note that in the context of the  Majority\xspace 
Bit Dissemination\xspace problem, the legality criteria depends on the initial configuration (that may be set by an adversary). That is, the agents must converge their opinion\xspace on the majority of input bits of sources, as evident in the initial configuration. 


The system\xspace is said to {\em stabilize} in $t$ rounds if, from any initial configuration w.h.p.,
within $t$ rounds it reaches a legal configuration and remains legal for at least some polynomial time  \cite{BCN15b,BCN16,DGM11}. In fact, for the self-stabilizing Bit Dissemination\xspace problem, if there are no conflicting source agents holding a minority opinion (such as in the case of a single source agent), then our protocols guarantee that once a legal configuration is reached, it remains legal~indefinitely. 
Note that, for any of the problems, we do not require that each agent irrevocably commits to
a final opinion\xspace but that eventually agents arrive at a 
legal configuration without necessarily being aware of that.



\subsection{Our Results}\label{sec:our-results}

Our main results are the following.

\begin{theorem}\label{thm:multi}
    Fix an arbitrarily small constant $\epsilon>0$. There exists a  protocol, called \textsc{Syn-Phase-Spread}\xspace, which solves the Majority\xspace Bit Dissemination\xspace problem in a self-stabilizing manner in $\tilde{\mathcal O}(\log n)$ rounds%
    \footnote{With a slight abuse of notation, with $\tilde{\mathcal O}(f(n)g(T))$ we refer to $f(n)g(T) \log^{\mathcal O(1)}(f(n)) \log^{\mathcal O(1)}(g(T))$. All logarithms are in base $2$.}
    w.h.p using $3$-bit messages, provided that the majority bit is supported by at least a fraction $\frac 12 + \epsilon$ of the source agents.
\end{theorem}

\noindent Theorem \ref{thm:multi} is proved in Section \ref{sec:majority}.
The core ingredient of \textsc{Syn-Phase-Spread}\xspace is our construction of an efficient self-stabilizing $T$-Clock Synchronization\xspace protocol, which is used as a black-box. For this purpose, the case that interests us  is when  $T=\tilde\mathcal O(\log n)$. 
Note that in this case, the following theorem, proved in  Section \ref{sec:clock}, states that the convergence time of the Clock Synchronization algorithm is $\tilde{\mathcal O}(\log n)$.

\begin{theorem}\label{thm:main}
    Let $T$ be an integer. There exists a self-stabilizing $T$-Clock Synchronization\xspace protocol, called \textsc{Syn-Clock}\xspace, which
    employs only 3-bit messages, and synchronizes clocks\xspace modulo~$T$ within $\tilde{\mathcal O}(\log n \log T)$ rounds w.h.p. 
\end{theorem}

\noindent In addition to the self-stabilizing context our protocols can tolerate the presence of Byzantine agents, as long as their number is%
\footnote{Specifically, it is  possible to show that, as a corollary of our
    analysis and the fault-tolerance property of the analysis in \cite{DGM11},
    if $T \leq poly(n)$ then \textsc{Syn-Clock}\xspace can tolerate the presence of up to
    $\mathcal O(n^{1/2 - \varepsilon})$ Byzantine agents for any $\epsilon>0$. In
    addition, \textsc{Syn-Phase-Spread}\xspace can tolerate
    $\min\{(1-\epsilon)(k_{maj}-k_{min}),n^{1/2-\epsilon}\}$ Byzantine agents,
    where $k_{maj}$ and $k_{min}$ are the number of sources supporting the
    majority and minority opinions, respectively. Note that for the case of a
    single source ($k=1$), no Byzantine agents are allowed; indeed, a single
    Byzantine agent pretending to be the source with the opposite opinion\xspace can
    clearly ruin any protocol.}
$\mathcal O(n^{1/2 - \varepsilon})$. 
However, in order to focus on the self-stabilizing aspect of our results, in this work we do not explicitly address the presence of Byzantine agents.

The proofs of both Theorem \ref{thm:main} and Theorem \ref{thm:multi} rely on
recursively applying a new general compiler which can essentially transform
any self-stabilizing algorithm with a certain property (called ``the
bitwise-independence\xspace property'') that uses $\ell$-bit messages to one that uses
only $\lceil \log \ell\rceil +1$-bit messages, while paying only a small
penalty in the running time. This compiler is described in Section
\ref{sec:compiler}, in Theorem \ref{lem:saving}, which is also referred as
``the \corelem\xspace''. The structure between our different lemmas and results is
summarized in the picture below, Figure \ref{fig:bigscheme}.




It remains an open problem, both for the self-stabilizing Bit Dissemination\xspace problem and for the self-stabilizing Clock Synchronization problem,  whether the message size can be reduced to 2 bits or even to 1 bit, while keeping the running time poly-logarithmic. 

\begin{figure*}[!ht]
    \centering
    \includegraphics[width=0.9\textwidth]{pics/bigscheme.pdf}
    \caption{The structure of our arguments. Note that the Message Reduction Theorem  is used on three occasions.} \label{fig:bigscheme}
\end{figure*}

\subsection{Related work}
 

The computational study of abstract systems composed of simple individuals that interact using highly restricted and stochastic interactions has recently been gaining considerable attention in the community of theoretical computer science. Popular models include {\em population protocols} \cite{Pop1,Pop2,Pop-ss,Joffroy}, which typically consider constant  size individuals that interact in pairs (using constant size messages) in random communication patterns, and the {\em beeping} model \cite{beeping1,emek}, which assumes  a fixed network with extremely restricted communication. Our model also falls in this framework as we consider the $\mathcal{PULL}$ model \cite{DGH88, KSSV00, KDG03} with constant size messages. So far, despite interesting works that consider different fault-tolerant contexts \cite{Aspnes,Pop-ss,Joffroy}, most of the progress in this framework considered non-faulty scenarios. 


Information dissemination is one of the most well-studied topics in the community of distributed computing, see, {\em e.g.,} \cite{Aspnes,CHHKM12,DGH88,DF11a,DGM11,OHK14,KSSV00}. Classical examples include the {\em Broadcast} (also referred to in the literature as  {\em Rumor Spreading}) problem, in which a piece of information residing at one source agent is to be disseminated to the rest of the population\xspace, and  {\em majority-consensus} (here, called Majority\xspace Bit Dissemination\xspace) problems in which processors are required to agree on a common output value which is the majority initial input value among all agents~\cite{Aspnes,kutten} or among a set of designated source agents \cite{OHK14}. An extensive amount of research has been dedicated to study such problems in $\mathcal{PUSH} / \mathcal{PULL}$ based protocols (including the {\em phone call} model), due to the inherent simplicity and fault-tolerant resilience of such meeting patterns. Indeed, the robustness of $\mathcal{PUSH} / \mathcal{PULL}$ based protocols to weak types of faults, such as crashes of messages and/or agents, or to the presence of relatively few Byzantine agents, has been known for quite a while \cite{ES09,KSSV00}. 
Recently, it has been shown that under the $\mathcal{PUSH}$ model, there exist  efficient Broadcast and Majority\xspace Bit Dissemination\xspace protocols that use a single bit per message and can overcome flips in messages (noise) \cite{OHK14}. The protocols therein, however, heavily rely on the assumption that agents know when the protocol has started. Observe that in a self-stabilizing context, in which the adversary can corrupt the initial clocks\xspace setting them to arbitrary times, such an assumption would be difficult to remove while preserving the small message size.

In general, there are only few known self-stabilizing protocols that operate
efficiently under stochastic and capacity restricted interactions. An example,
which is also of high relevance to this paper, is the work of Doerr et al. on
{\em Stabilizing Consensus} \cite{DGM11} operating in the  $\mathcal{PULL}$ model. In
that work, each agent initially has a state taken out of a set of $m$
opinions\xspace and the goal is to converge on one of the proposed states. The
proposed algorithm which runs in logarithmic time is based on sampling the
states of $2$ agents and updating the agent's state to be the median of the $2$
sampled states and the current state of the agent ($3$ opinions\xspace in total).
Since the total number of possible states is $m$, the number of bits that must
be revealed in each interaction is $\Omega(\log m)$. 
Another example is the plurality consensus protocol in \cite{BCN16}, in which each agent has initially an opinion and we want the system to converge to the most frequent one in the initial configuration of the system.
In fact, the Majority\xspace Bit Dissemination\xspace problem can be viewed as a generalization of the {\em majority-consensus} problem (i.e. the plurality consensus problem with two opinions), to the case in which multiple agents may initially be unopinionated. In the previous sense, we also contribute to the line of research on the majority-consensus problem  \cite{BCN15, CER15, EFK16}.


Another fundamental building block is Clock Synchronization  \cite{Attiya,Lamport,Lenzen3,Lenzen2}. 
We consider a synchronous system in which clocks tick at the same pace but may
not share the same opinion\xspace. This version  has earlier been studied in e.g.,
\cite{Ben-Or,Dolev07,Dolev97,Dolev04,SIROCCO,Herman} under different names,
including ``digital Clock Synchronization'' and ``synchronization of
phase-clocks''; We simply use the term ``Clock Synchronization''. There is by
now a substantial line of work on Clock Synchronization problems in a
self-stabilizing context \cite{DolevKLRS13, Dolev04, Lenzen4, Lenzen5}. We note
that in these papers the main focus is on the resilience to Byzantine agents.
The number of rounds and message lengths are also minimized, but typically as a
function of the number of Byzantine processors. Our focus is instead on
minimizing the time and message complexities as much as possible. The authors
in \cite{Lenzen4, Lenzen5} consider mostly a deterministic setting. The
communication model is very different than ours, as every agent gets one
message from every other agent on each round. Moreover, agents are assumed to
have unique identifiers. In contrast, we work in a more restricted, yet
randomized communication setting. In \cite{DolevKLRS13, Lenzen4} randomized
protocols are also investigated. We remark that the first protocol we discuss
\textsc{Syn-Simple}\xspace (Proposition \ref{prop:simple}), which relies on a known simple
connection between consensus and counting \cite{DolevKLRS13}, already improves
exponentially on the randomized algorithms from \cite{DolevKLRS13, Lenzen4} in
terms of number of rounds, number of memory states, message length and total
amount of communication, in the restricted regime where the resilience
parameter $f$ satisfies $ \log n \leq f \leq \sqrt{n}$. We further note that
the works \cite{Lenzen5,Lenzen4} also use a recursive construction for their
clocks\xspace (although very different from the one we use in the proof of
Theorem~\ref{thm:main}). The induction in \cite{Lenzen4} is on the resilience
parameter $f$, the number of agents and the clock\xspace length together.
This idea is improved in \cite{Lenzen5}  to achieve optimality in terms of
resilience to Byzantine agents. 
 

To the best of our knowledge there are no previous works on self-stabilizing Clock Synchronization or Majority Bit Dissemination that aim to minimize the message size beyond logarithmic.

\section{Preliminaries}\label{sec:Preliminaries}

\subsection{A majority based, self-stabilizing protocol for consensus on one bit}

Let us recall%
\footnote{Our protocols will use this protocol as a \emph{black box}. However,
we note that  the constructions we outline are in fact independent of the
choice of consensus protocol, and this protocol could be replaced by other
protocols that achieve similar guarantees.} 
the stabilizing consensus protocol by Doerr et al. in \cite{DGM11}.  
In this protocol, called \textsc{maj-consensus}\xspace, each agent holds  an opinion\xspace. In  each
round each agent looks at the opinions\xspace of two other random agents and
updates her opinion\xspace  taking the majority among the bits of the observed
agents and its own. 
Note that this protocol uses only a single bit per interaction, namely, the
opinion\xspace. The usefulness of \textsc{maj-consensus}\xspace comes from its extremely fast and
fault-tolerant convergence toward an agreement among agents, as given by the
following~result.
 
\begin{theorem}[Doerr et al. \cite{DGM11}]\label{thm:doerr}
    From any initial configuration,  \textsc{maj-consensus}\xspace converges to a state in which all
    agents agree on the same output bit in $\mathcal O(\log n)$ rounds, w.h.p.
    Moreover, if there are at most $\kappa \leq n^{1/2-\varepsilon}$ Byzantine
    agents, for any constant $\epsilon>0$, then after $\mathcal O(\log n)$ rounds
    all non-Byzantine agents have converged and consensus is maintained for
    $n^{\Omega(1)}$ rounds w.h.p.%
    \footnote{The original statement of \cite{DGM11} says that if at most
        $\kappa \leq \sqrt n$ agents can be corrupted at any round, then convergence
        happens for all but at most $\mathcal O(\kappa)$ agents. Let us explain how this
        implies the statement we gave, namely that we can replace $\mathcal O(\kappa)$
        by $\kappa$, if $\kappa \leq n^{\frac{1}{2}-\varepsilon}$. Assume that we
        are in the regime $\kappa \leq n^{\frac{1}{2}-\varepsilon}$. It follows
        from \cite{DGM11} that all but a set of $\mathcal O(\kappa)$  agents reach
        consensus after $\mathcal O(\log n)$ round. This set of size $\mathcal O(\kappa)$
        contains both Byzantine and non Byzantine agents. However, if the number of
        agents holding the minority opinion\xspace is $\mathcal O(\kappa ) =
        \mathcal O(n^{1/2-\varepsilon})$, then the expected number of non Byzantine
        agents that disagree with the majority \emph{at the next round} is in
        expectation $\mathcal O(\kappa^2 /n) = \mathcal O(n^{- 2\varepsilon} )$.
        Thus, by Markov's inequality,  this  implies, that at the next round
        consensus is reached among \emph{all non-Byzantine agents} w.h.p. Note also
        that, for the same reasons, the Byzantine agents do not affect any other
        non-Byzantine agent for $n^{\varepsilon} $ rounds w.h.p.}
    \label{thm:maj_consensus}
\end{theorem}





\subsection{Protocol \textsc{Syn-Simple}\xspace: A simple protocol with many bits per interaction}\label{sec:simple}
We now present a simple self-stabilizing $T$-Clock Synchronization protocol, called  \textsc{Syn-Simple}\xspace, that uses relatively many bits per message, and relies on the assumption that $T$ is a power of 2. The protocol is based on iteratively applying a self-stabilizing consensus protocol on each bit of the clock separately, and in parallel. 

Formally, each agent $u$ maintains  a clock $C_u \in [0, T-1]$.
At each round,  $u$ displays the opinion\xspace of her clock $C_u$, pulls~$2$ uniform other such clock opinions\xspace, and updates her clock as the bitwise majority of the 
two clocks it pulled, and her own.
Subsequently, the clock $C_u$ is incremented.
We present the pseudo code of \textsc{Syn-Simple}\xspace in Algorithm \ref{alg:simple}. 

\begin{pseudocode}[!ht]
    \textbf{\textsc{Syn-Simple}\xspace protocol}

    \smallskip
    \begin{description}
        \item[1] $u$ samples two agents $u_1$ and $u_2$.
        \item[2] $u$ updates its clock with the bitwise majority of its clock and those
            of the sample nodes.
        \item[3] $u$ increments its clock by one unit. \label{line:Qincr}
    \end{description}
    \caption{One round of \textsc{Syn-Simple}\xspace, executed by each agent $u$.}
    \label{alg:simple}
\end{pseudocode}

We prove the correctness of \textsc{Syn-Simple}\xspace in the next proposition.

\begin{proposition}\label{prop:simple}
    Let $T$ be a power of $2$. The protocol \textsc{Syn-Simple}\xspace is  a self-stabilizing protocol that uses $\mathcal O(\log T) $ bits per interaction and synchronizes clocks modulo $T$ in $\mathcal O(\log T \log n)$ rounds w.h.p. 
\end{proposition}
\begin{proof}
    Let us look at the least significant bit. One round of \textsc{Syn-Simple}\xspace is
    equivalent to one round of \textsc{maj-consensus}\xspace with an extra flipping of the opinion\xspace
    due to the increment of the clock. The crucial point is that all agents
    jointly flip their bit on every round. Because the function agents apply,
    \textsc{maj}, is symmetric, it commutes with the flipping operation. More
    formally, let $\vec{b}_{t}$ be the vector of the first bits of the clocks
    of the agents at round $t$ under an execution of \textsc{Syn-Simple}\xspace.
    E.g. $(\vec{b}_{t})_u$ is the value of the less significant bit of node
    $u$'s clock at time $t$.
    %
    Similarly, we denote by $\vec{c}_t$ the first bits of the clocks of the
    agents at round $t$ obtained by running a modified version of \textsc{Syn-Simple}\xspace in
    which {\em time is not incremented} (i.e. we skip line \ref{line:Qincr} in
    Algorithm \ref{alg:simple}). We couple $\vec{b}$ and $\vec{c}$ trivially,
    by running the two versions on the same interaction pattern (in other
    words, each agent starts with the same memory and pulls the same agents at
    each round in both executions).
    %
    Then, $\vec{b_t}$ is equal to $\vec{c_t}$ when $t$ is even, while is equal to
    $\vec{b_t} = \mathbf{1}-\vec{c_t}$ when $t$ is odd.
    %
    Moreover, we know from Theorem \ref{thm:doerr} that $\vec{c_t}$ converge to
    a stable opinion\xspace in a self-stabilizing manner. It follows that, from any
    initial configuration of states (i.e. clocks), w.h.p, after $\mathcal O(\log n)$
    rounds of executing \textsc{Syn-Simple}\xspace, all agents share the same opinion\xspace for their
    first bit, and jointly flip it in each round.
    %
    Once agents agree on the first bit, since $T$ is a power of $2$, the
    increment of time makes them flip the second bit \emph{jointly} once every
    $2$ rounds%
    \footnote{To get the feeling of the kind of dependence more significant
    bits have on the less significant ones when $T$ is not a power of $2$
    observe that, for example, if $T=3$ then the first bit takes cyclically the
    values $1$, $0$ and again $0$.}.
    %
    More generally, assuming agents agree on the first $\ell$ bits of their
    clocks, they \emph{jointly} flip the $\ell +1$'st bit once every $2^{\ell}$
    rounds, on top of doing the $\textsc{maj-consensus}\xspace$ protocol on that bit.
    %
    Hence, the same coupling argument shows that the flipping doesn't affect the
    convergence on bit $\ell +1$. Therefore, $\mathcal O(\log n)$ rounds after the
    first $\ell$ bits are synchronized, w.h.p. the $\ell+1$'st bit is synchronized as
    well. The result thus follows by induction.
\end{proof}

\subsection{The bitwise-independence\xspace property}\label{sec:property}

Our general transformer described in Section \ref{sec:compiler} is useful for reducing the message size of protocols with a certain property called bitwise-independence\xspace. 
Before defining the property we need to define a variant of the $\mathcal{PULL}$ model, which we refer to as the $\mathcal{BIT}$ model. The reason we introduce such a variant is mainly technical, as it appears naturally in our proofs.

Recall that in the $\mathcal{PULL}(\eta,\ell)$ model, at any given round, each agent $u$ is reading an $\ell$-bit  message $m_{v_j}$ for each of the  $\eta$ observed agents $v_j$ chosen u.a.r. (in our case $\eta=2$), and then, in turn, $u$  updates her state according to the instructions of a protocol \textsc{P}\xspace.
Informally, in the $\mathcal{BIT}$ model, each agent $u$ also receives $\eta$ messages, however, in contrast to the $\mathcal{PULL}$ model where each such message corresponds to one observed agent, in the $\mathcal{BIT}$ model, the $i$'th bit of each such message is received independently from a (typically new) agent, chosen u.a.r. from all agents. 
\begin{definition}[The $\mathcal{BIT}$ model]\label{def-bits}
  In the $\mathcal{BIT}$ model,
  at each round, each agent $u$
  picks  $\eta\ell$ agents u.a.r., namely, $v_1^{(1)},v_2^{(1)}, \ldots v_{\ell}^{(1)}$,\ldots,$v_1^{(\eta)},v_2^{(\eta)}, \ldots v_{\ell}^{(\eta)}$, and reads $\hat{ s_i}^{(j)} = s_i(v_i^{(j)})$, the $i$-th bit of the visible part of agent $v_i^{(j)}$, for every $i \leq \ell$ and $j \leq \eta$.
  %
  For each $j \leq \eta$, let $\hat{m_j}(u)$ be the $\ell$-bit string $\hat{m_j}(u):= (\hat{s_1}^{(j)},\hat{s_2}^{(j)},\dots, \hat{s_\ell}^{(j)})$. 
  By a slight abuse of language we call the strings $\{\hat{m_j}(u)\}_{j\leq \eta}$
  the \emph{messages} received by $u$ in the $\mathcal{BIT}$ model.
\end{definition}

\begin{definition}[The $bitwise-independence\xspace$ property]\label{def:ip}
  Consider a protocol \textsc{P}\xspace designed to work in the $\mathcal{PULL}$ model. We say that \textsc{P}\xspace has the bitwise-independence\xspace property if its correctness and running time guarantees remain the same, under the $\mathcal{BIT}$ model (assuming that given the messages $\{\hat{m_j}(u)\}_{j\leq \eta}$ it receives at any round, each agent $u$ performs the same actions that it would have, had it received these messages in the $\mathcal{PULL}$ model).
\end{definition} 

Let us first state a fact about protocols having the bitwise-independence\xspace property.
\begin{lemma}\label{lem:ipfact}
    Assume protocol \textsc{Syn-Generic}\xspace is a protocol synchronizing clocks\xspace modulo $T$ for some $T$ and protocol \textsc{P}\xspace is a protocol which works assuming agents share a clock modulo $T$.
    Denote by \textsc{Syn-P}\xspace the parallel execution of \textsc{Syn-Generic}\xspace and \textsc{P}\xspace, with \textsc{P}\xspace using the clock synchronized by \textsc{Syn-Generic}\xspace. 
    If \textsc{Syn-Generic}\xspace and \textsc{P}\xspace are self-stabilizing then so is \textsc{Syn-P}\xspace, and the
    convergence time of \textsc{Syn-P}\xspace is at most the sum of convergence times of
    \textsc{Syn-Generic}\xspace and \textsc{P}\xspace.
   
    Finally, if \textsc{Syn-Generic}\xspace and \textsc{P}\xspace have the bitwise-independence\xspace property, and \textsc{P}\xspace is also self-stabilizing, \textsc{Syn-P}\xspace has the bitwise-independence\xspace property too.
\end{lemma}
\begin{proof}
    The self-stabilizing property of \textsc{Syn-P}\xspace and its convergence time easily follows from those of \textsc{Syn-Generic}\xspace and \textsc{P}\xspace. 
    
    As for the bitwise-independence\xspace property, assume we run \textsc{Syn-P}\xspace in the
    $\mathcal{BIT}$ model. The execution of \textsc{Syn-Generic}\xspace is carried independently of
    the execution of \textsc{P}\xspace.
    %
    Since, by hypothesis, \textsc{Syn-Generic}\xspace has the independence property, eventually all
    agents have a synchronized clock\xspace modulo $T$. Thus, once clocks\xspace are
    synchronized, we can disregard the part of the message corresponding to
    \textsc{Syn-Generic}\xspace, and view the execution of \textsc{Syn-P}\xspace as simply \textsc{P}\xspace. 
    %
    Therefore, since \textsc{P}\xspace is self-stabilizing and has the independence
    property, \textsc{Syn-P}\xspace still works in the $\mathcal{BIT}$ model as in the
    original $\mathcal{PULL}$ model.
\end{proof}

\noindent We next show that the protocol \textsc{Syn-Simple}\xspace has the aforementioned bitwise-independence\xspace property.

\begin{lemma}\label{lem:simple_ind}
    \textsc{Syn-Simple}\xspace has the bitwise-independence\xspace property. 
\end{lemma}
\begin{proof}
    Let $\ell'$ be the size of the clocks\xspace. 
    Assume the first $i<\ell'$ bits of the clocks\xspace have been synchronized. At
    this stage, the $(i+1)$-st bit of each agent $u$ is flipped every $2^{i}$
    rounds and updated as the majority of the $(i+1)$-st bit of $C(u)$ and the $2$
    pulled messages on each round. 
    Since the first $\ell'$ bits are synchronized, the previous flipping is
    performed by all agents at the same round.
    %
    The thesis follows from the observation that, in order for \textsc{Syn-Simple}\xspace to work,
    we do not need the bit at index $(i+1)$ to come from the same agent as
    those bits used to synchronize the other indices, as long as convergence on
    the first $i$ bits has been achieved. 
\end{proof}


\section{A General Compiler that Reduces Message Size}\label{sec:compiler}


In this section we present a general compiler that allows to implement a protocol \textsc{P}\xspace using $\ell$-bit messages while using messages of order $\log \ell$ instead, as long as \textsc{P}\xspace enjoys the  bitwise-independence\xspace property. The compiler is based on replacing a message by an index to a given bit of the message. This tool will repeatedly be used in the following sections to obtain our Clock Synchronization and Majority\xspace Bit Dissemination\xspace algorithms that use 3-bit messages.


\begin{theorem}[the \corelem\xspace]\label{lem:saving}
    Any self-stabilizing protocol \textsc{P}\xspace in the $\mathcal{PULL}(\eta,\ell)$ model having the bitwise-independence\xspace property, and whose running time is $L_{\protocol} $, can be emulated by a protocol \textsc{Emul(\textsc{P}\xspace)}\xspace which runs in the $\mathcal{PULL}(2,\lceil \log ( \frac{\mesnum}{2} \ell) \rceil + 1)$ model, has running time $\mathcal O\left(\log (
    \eta \ell) \log n +  \frac{\mesnum}{2}  \ell L_{\protocol}  \right)$ and has itself the bitwise-independence\xspace property. 
\end{theorem}
\begin{remark}
The only reason for designing \textsc{Emul(\textsc{P}\xspace)}\xspace to run in the $\mathcal{PULL}(2,\lceil \log ( \frac{\mesnum}{2} \ell)  \rceil + 1)$ model in the \corelem\xspace is the consensus protocol we adopt, \textsc{maj-consensus}\xspace, which works in the $\mathcal{PULL}(2)$ model. In fact, \textsc{Emul(\textsc{P}\xspace)}\xspace can be adapted to run in the $\mathcal{PULL}(1,\lceil \log (\eta\ell)  \rceil + 1)$ model by using a  consensus protocol which works in the $\mathcal{PULL}(1)$ model. However, no self-stabilizing binary consensus protocol in the $\mathcal{PULL}(1)$ model with the same performances as \textsc{maj-consensus}\xspace is currently known.
\end{remark}
\proofof{Theorem \ref{lem:saving}}
    Let $s(u) \in \{0,1 \}^{\ell}$ be the message displayed by an agent $u$
    under \textsc{P}\xspace at a given round. For simplicity's sake, in the following
    we assume that $\eta$ is even, the other case is handled similarly. In
    \textsc{Emul(\textsc{P}\xspace)}\xspace, agent $u$ keeps the message~$s(u)$ privately, and instead displays a
    clock\xspace $C(u)$ written on $\lceil \log ( \frac{\mesnum}{2} \ell)
    \rceil$  bits, and one bit of the message~$s(u)$, which we refer to as the
    $\textsc{P}\xspace$-bit. 
    %
    Thus, the total number of bits displayed by the agent operating in \textsc{Emul(\textsc{P}\xspace)}\xspace is
    $\lceil \log ( \frac{\mesnum}{2}  \ell) \rceil +1$.
    %
    The purpose of the clock\xspace $C(u)$ is to indicate to agent $u$ which
    bit of $s(u)$ to display. In particular, if the counter has value $0$, then
    the $0$-th bit (i.e the least significant bit) of $s(u)$ is shown as the
    \textsc{P}\xspace-bit, and so on. In what follows, we refer to $s(u)$ as the {\em
    private message} of $u$, to emphasize the fact that this message is not
    visible in \textsc{Emul(\textsc{P}\xspace)}\xspace. See Figure \ref{fig:savingfig} for an illustration.

    \begin{figure*}[!ht]
        \centering
        \includegraphics[width=1\textwidth]{pics/savingfig2.pdf}
        \caption{On the left is a protocol \textsc{P}\xspace using $\ell =8$ bits in
            total and pulling only one node per round ($\eta=1$). On the right
            is the emulated version \textsc{Emul(\textsc{P}\xspace)}\xspace which uses $4$ bits only. The bits
            depicted on the bottom of each panel are kept privately, while the bits
            on the top are public, that is, appear in the visible part.} 
        \label{fig:savingfig}
    \end{figure*}

    Each round of \textsc{P}\xspace executed in the $\mathcal{PULL}(\eta,\ell)$ model by an
    agent $u$ is emulated by $  \frac{\mesnum}{2}  \ell$ rounds of  \textsc{Emul(\textsc{P}\xspace)}\xspace in
    the $\mathcal{PULL}(2,\lceil \log ( \frac{\mesnum}{2} \ell) \rceil + 1)$ model. 
    %
    We refer to such $  \frac{\mesnum}{2}  \ell$ rounds as a {\em phase},
    which is further divided to $ \frac{\mesnum}{2} $ subphases of length
    $\ell$. Note that since each agent samples 2 agents in a round, the
    total number of agents sampled by an agent during a phases is $\eta
    \ell$.  
     
    For a generic agent $u$, a phase starts when its clock\xspace $C(u)$ is
    zero, and ends after a full loop of its clock\xspace (i.e. when $C(u)$
    returns to zero). Each agent $u$ is running protocol \textsc{Syn-Simple}\xspace on the $\lceil
    \log ( \frac{\mesnum}{2}  \ell) \rceil$  bits which correspond to her
    clock\xspace $C(u)$. 
    %
    Note that the phases executed by different agents may initially be
    unsynchronized, but, thanks to Proposition \ref{prop:simple}, the clocks\xspace 
    $C(u)$ eventually converge to the same value, for each agent $u$, and
    hence all agents eventually agree on when each phase (and subphase) starts. 

    Let $u$ be an arbitrary agent.
    %
    Denote by $\hat s_1^{(1)}, \hat s_2^{(1)}, \ldots \hat s_\ell^{(1)}$, ...,
    $\hat s_1^{(\eta)}, \hat s_2^{(\eta)}, \ldots \hat
    s_\ell^{(\eta)}$  the \textsc{P}\xspace-bits collected by $u$ from agents chosen
    u.a.r during a phase.
    %
    Consider a phase and a round $z\in \{1,\cdots,  \frac{\mesnum}{2} 
    \ell\}$ in that phase. Let $i$ and $j$ be such that $z=j\cdot
    \ell + i$. We view $z$ as round $i$ of subphase $j+1$ of the
    phase. 
    %
    On this round, agent $u$ pulls two messages from agents $v$ and $w$, chosen u.a.r.
    %
    Once the clocks (and thus phases and subphases) have synchronized, agents
    $v$ and $w$ are guaranteed to be displaying the $i$th index of their
    private messages, namely, the values $s_i(v)$ and $s_i(w)$, respectively.
    %
    Agent $u$ then sets $\hat s_i^{(2j-1)}$ equal to $ s_i(v)$ and
   
   
    $\hat s_i^{(2j)}$ equal to $s_i(w)$.

    In  \textsc{Emul(\textsc{P}\xspace)}\xspace, the messages displayed by agents are only updated after a full
    loop of $C$. It therefore follows from the previous paragraph that the
    \textsc{P}\xspace-bits collected by agent $u$ after a full-phase are distributed
    like the bits collected during one round of \textsc{P}\xspace in the
    $\mathcal{BIT}$ model (see Definition \ref{def-bits}), assuming the
    clocks\xspace are synchronized already.

    \smallskip
    \noindent \emph{Correctness.} 
    The bitwise-independence\xspace property of \textsc{Syn-Simple}\xspace (Lemma \ref{lem:simple_ind}), implies
    that \textsc{Syn-Simple}\xspace still works when messages are constructed from the
    \textsc{P}\xspace-bits collected by \textsc{Emul(\textsc{P}\xspace)}\xspace. Therefore, from Proposition
    \ref{prop:simple}, eventually all the clocks\xspace $C$ are synchronized. 
    %
    Since private messages $s$ are only updated after a full loop of $C$, 
    once the clocks\xspace $C$ are synchronized a phase of \textsc{Emul(\textsc{P}\xspace)}\xspace corresponds to
    \emph{one} round of \textsc{P}\xspace, executed in the $\mathcal{BIT}$ model.
    Hence, the hypothesis that \textsc{P}\xspace operates correctly in a
    self-stabilizing way in the $\mathcal{BIT}$ model implies the correctness
    of \textsc{Emul(\textsc{P}\xspace)}\xspace.

    \smallskip
    \noindent\emph{Running time.}
    Once the clocks\xspace $C(u)$ are synchronized, for all agents $u$, 
    using the first $\lceil \log ( \frac{\mesnum}{2}  \ell) \rceil$ bits of the messages,
    the agents reproduce an execution of \textsc{P}\xspace with a multiplicative time-overhead of $ \frac{\mesnum}{2}  \ell$. 
    Moreover, from Proposition \ref{prop:simple}, synchronizing the clocks $C(u)$ takes $\mathcal O\left(\log (\eta m) \log n\right)$ rounds.
    Thus, the time to synchronize the clocks\xspace costs only an additive factor of $\mathcal O\left(\log (\eta m) \log n\right)$ rounds, and the total running time is  $\mathcal O\left(\log (\eta m) \log n \right) +  \frac{\mesnum}{2}  \ell \cdot L_{\protocol} $.

    \smallskip
    \noindent\emph{Bitwise-independence property.}
    %
    Protocol \textsc{Emul(\textsc{P}\xspace)}\xspace inherits the bitwise-independence\xspace property from that of \textsc{Syn-Simple}\xspace
    (Lemma \ref{lem:simple_ind}) and \textsc{P}\xspace (which has the property by
    hypothesis):
    %
    We can apply Lemma \ref{lem:ipfact} where \textsc{Syn-Generic}\xspace is \textsc{Syn-Simple}\xspace and \textsc{P}\xspace is
    the subroutine described above, which displays at each round the bit of $P$
    whose index is given by a synchronized clock\xspace $C$ modulo $\ell$
    (i.e. the one produced by \textsc{Syn-Simple}\xspace). Observe that the aforementioned
    subroutine is self-stabilizing, since it emulates \textsc{P}\xspace once clocks\xspace
    are synchronized. Then, in the notation of Lemma \ref{lem:ipfact}, \textsc{Emul(\textsc{P}\xspace)}\xspace is
    \textsc{Syn-P}\xspace. 
\hspace{\stretch{1}$\square$}

\section{Self-Stabilizing Clock Synchronization}
\label{sec:clock}
In Section \ref{sec:simple} we described \textsc{Syn-Simple}\xspace ~-~ a simple self-stabilizing Clock Synchronization protocol that  uses $\log T$ bits per interaction. In this section we describe our main self-stabilizing Clock Synchronization protocol, \textsc{Syn-$3$Bits}\xspace, that uses only $3$ bits per interaction.
We first assume $T$ is a power of $2$. We show  how to get rid of this assumption in Section~\ref{sub:powerof}. 

\subsection{Clock Synchronization with $3$-bit messages, assuming $T$ is a power of two}
\label{sec:analysisthree}

\begin{figure*}[!ht]
    \centering
    \includegraphics[width=0.7\textwidth]{pics/clocks_on_top.pdf}
    \caption{A more explicit view of our $3$-bit emulation of protocol
        \textsc{P}\xspace, obtained by iterating Lemma \ref{lem:saving}. The down-most
        layer represents the $2^7$-bits message displayed by protocol
        \textsc{P}\xspace. Each layer on the picture may be seen as the message of a
        protocol emulating \textsc{P}\xspace with fewer bits, that is, as we go up on
        the figure we obtain more and more economical protocols in terms of
        message length. In particular, the top layer represents the  $3$-bit
        message in the final emulation. The left-most part of each message
        (colored in light blue) encodes a clock\xspace. The right-most bit (colored
        in light yellow) of each message (except the bottom-most one)
        corresponds to a particular bit of the layer \emph{below} it. The index
        of this particular displayed bit is given by the value of the clock\xspace.
        Each clock\xspace on an intermediate layer is updated only when the
        clock\xspace on the layer \emph{above} completes a loop (i.e., has value
        $0$). The clock\xspace on the top-most layer is updated on every round.} 
    \label{fig:clocklayers}
\end{figure*}

In this section, we show the following result.
\begin{lemma}\label{lem:threebits}
    Let $T$ be a power of $2$. There exists a synchronization protocol
    \textsc{Syn-Intermediate}\xspace which synchronizes clocks\xspace modulo $T$ in time $ \tilde{\mathcal O}\left(\log^2 T \log n\right)$ using only 3-bit messages. Moreover, \textsc{Syn-Intermediate}\xspace has the bitwise-independence\xspace property.
\end{lemma}

Before presenting the proof of Lemma \ref{lem:threebits}, we need a remark about clocks\xspace.
\begin{remark}\label{rem:counters}
    In order to synchronize a clock $C$ modulo $T$, throughout the analysis we
    often obtain a clock $C'$ modulo $T$ \emph{which is incremented every $\ell$
    rounds}. However, $C'$ can still be translated back to a clock modulo
    $T$ which is incremented every round, by keeping a third clock $C''$ modulo
    $\ell$ and setting 
    \[
        C = C' + C'' \mod T.
    \]
\end{remark}

\proofof{Lemma \ref{lem:threebits}}
    At a high level, we simply apply iteratively the \corelem\xspace in order to reduce
    the message to $3$ bits, starting with \textsc{P}\xspace = \textsc{Syn-Simple}\xspace.
    %
    A pictorial representation of our recursive protocol is given in Figure
    \ref{fig:clocklayers}, and a pseudocode is given in Algorithm \ref{alg:intermediate}%
    \footnote{The pseudocode deviates from the presentation done in the proof,
    as it makes no use of recursion.}.

    Let us consider what we obtain after applying the \corelem\xspace
    the 
    first time to \textsc{P}\xspace $=$\textsc{Syn-Simple}\xspace for clocks modulo $T$. 
   
    Recall that we assume that $T$ is a power of 2. 
    From Proposition \ref{prop:simple} we know that in this case, the
    convergence time of \textsc{Syn-Simple}\xspace is $L_{\protocol}  = \mathcal O\left( \log T \log
    n\right)$, the number of pulled agents at each round is $2$ and
    the number of bits of each message is $\ell = \log T$. 
    %

    With the emulation produced by the \corelem\xspace, the clock\xspace used in \textsc{P}\xspace =\textsc{Syn-Simple}\xspace is incremented only every $\ell =\log T$ rounds. 
   
    Another way to interpret this is that we obtain a clock\xspace modulo $T\cdot \ell$ and using Remark \ref{rem:counters} we can view the clock $C:=T\cdot \ell \mod T$,
    as a counter modulo $T$ that is incremented at each round. 
    Hence, by the running time analysis of the \corelem\xspace, we obtain a protocol $\textsc{Emul(\textsc{P}\xspace)}\xspace$ which synchronizes a clock\xspace modulo $T$ in
    $\mathcal O\left(\log n\log \log T \right) + \mathcal O\left(\log^2 T \log n\right) = \mathcal O\left( \log^2 T \log n\right)$ rounds. 
    The message size is reduced from $\log T$ to $\lceil \log \log T \rceil +1 = \mathcal O\left(\log \log T \right)$.

    By repeatedly applying the \corelem\xspace, we reduce the size of the message $\ell$ as long as $\ell > \lceil \log \ell \rceil +1$, i.e. as long as $\ell>3$. 
    %
    The number of repeated application of the \corelem\xspace until the message size is $3$ is thus of order $\log^{*} T$. 

    \begin{pseudocode}[!ht]
        \textbf{\textsc{Syn-Intermediate}\xspace protocol}

        \smallskip
        \textsc{Memory:}
        Each agent $u$ keeps a sequence of clocks\xspace $C_1,\ldots,
        C_\tau$ and a sequence of bits $b_1, \ldots,
        b_\tau$. The clock $C_1$ runs modulo $T$, the clock\xspace
        $C_\tau$ runs modulo $4$, and the $i$-th clock\xspace
        $C_i$ runs modulo $2^{\ell_i-1}$ (see proof of Lemma
        \ref{lem:threebits}).
        %
        Each agent $u$ also maintains a sequence of heaps (or some ordered
        structure) $S^{\delta}_i$, for each $\delta \in \{1, 2\}$ and $i =
        1,\ldots, \tau$.

        \smallskip
        \textsc{Message:} 
        $u$ displays $C_\tau$ ($2$ bits) and $b_\tau$ ($1$
        bit). For all $i \in [\tau], b_i(u)$ is the
        $C_i(u)$-th bit of the string obtained concatenating the
        binary representation of $C_{i-1}(u)$ and $b_{i-1}(u)$.

        \smallskip
        \begin{description}
            \item[1] $u$ samples two agents $u_1$ and $u_2$.
            \item[2] $u$ updates its clock with the bitwise majority of its clock and those
                of the sampled nodes.
            \item[3] $u$ increments its clock by one unit.
            \item[4] $u$ sets $i^*$ equal to the maximal $i< \tau$
                such that $C_{i+1} \neq 0$.
            \item[5] For $\delta=1,2$, $u$ pushes $b_\tau(u_\delta)$ in $S^{\delta}_{i^*}$.\\
                (Note that, if $C_{i^*+1}, \ldots, C_{\tau}$ are
                synchronized, then all agents are displaying the bit with index
                $C_{i^*+1}$ of $(C_{i^*},b_{i^*})$ as $b_{\tau}$.)
            \item[6] {While} $i>1$ and $C_{i} = 0$, $u$ does the following:
                \item[7] \hspace{.2cm}$|$\hspace{.2cm} Pops the last $\ell_{i-1}-1$ bits from $S^\delta_{i-1}$ and 
                    set $s^\delta$ equal to it. 
                \item[8] \hspace{.2cm}$|$\hspace{.2cm} Sets $C_{i-1}$ equal to the bitwise majority of
                    $C_{i-1}(u)$, $s^{1}$ and $s^{2}$.
                \item[9] \hspace{.2cm}$|$\hspace{.2cm} Increments $C_{i-1}$ and
                    decrement $i$ by one unit.
        \end{description}
        %
        \caption{Iterative version of the protocol \textsc{Syn-Intermediate}\xspace,
            executed by each agent $u$, unfolding the recursion in proof of
            Lemma \ref{lem:threebits}.}
        \label{alg:intermediate}
    \end{pseudocode}

    Let us analyze the running time. 
    Let $\ell_1 = \log T$, $\ell_{i+1} =  \lceil \log \ell_i \rceil +1$
    and let $\tau(T) = \tau$ be the smallest integer such that $\ell_\tau= 3$.
    %
    We apply the \corelem\xspace $i\leq \tau$ times, and we obtain a message size $\ell_i$ and a running time $L_i$, such that 
    \begin{align}
        L_{i+1} \leq \gamma_1(\log \ell_i \log n + \ell_i L_i),
        \label{eq:recruntime}
    \end{align}
    for some constant $\gamma_1$ independent of $i$.
    We set $L_1$ to be
     $L_1 :=  L_{\textsc{Syn-Simple}\xspace} \vee \log n =  \mathcal O\left(\log T \log n\right) \vee \log n$, taking the maximum with $\log n$ for technical convenience. 
    The second term dominates in (Equation \ref{eq:recruntime}) because $\ell_i >> \log \ell_i$ and $L_i > \log n$. Hence $L_i$ is at most of order $\prod_{j<i} \ell_j\cdot L_1$. More precisely, by induction we can bound $L_i \leq \gamma_1^i\prod_{j=1}^{i-1} \ell_{j} L_1$, since
    \begin{align}
        L_{i+1} 
        \leq \gamma_1\log \ell_i \log n + \gamma_1^i\prod_{j=1}^{i} \ell_{j} \cdot L_1
        \leq \gamma_1 \ell_i \log n + \gamma_1^i \prod_{j=1}^{i} \ell_j \cdot L_1 
        \leq 2\gamma_1^i \prod_{j=1}^{i} \ell_j \cdot L_1 
            \leq \gamma_1^{i+1} \prod_{j=1}^{i} \ell_j \cdot L_1,
    \end{align}
    where we use the fact that $\gamma_1 >2$, 
    and the definition of~$L_1$.

    The running time of \textsc{Emul(\textsc{P}\xspace)}\xspace$=$\textsc{Syn-Clock}\xspace after the last application of the \corelem\xspace, i.e. $\tau$, is thus
    \begin{align}
        L_{\synclock} := L_{\tau} \leq \gamma_1^{\tau} 
        \prod_{i=1}^{\tau} \ell_i L_1.
    \end{align}
   
    We use the following fact.
   
    %
    \begin{fact}
        \label{fact:exp_ineq}
        If $|x|<1$, it holds
        \[
        e^{\frac{x}{1+x}}\leq1+x\leq e^{x}\leq 1+\frac{x}{1-x}.
        \]
    \end{fact}
    %
    From the bounds 
    $L_1 = \mathcal O(\log T \log n)$, 
    $\prod_{i=1}^{\tau} \ell_i \leq \ell_1 \ell_2 \ell_3^{\tau}$, 
    $\ell_1 = \mathcal O\left(\log T\right)$, 
    $\ell_2 = \mathcal O\left(\log \log T\right)$ and Lemma \ref{lem:gt}, we obtain 
    $\gamma_1^{\tau} = \mathcal O\left(\log \log \log T\right)$ and
    \[
        \ell_3^{\tau} \leq 2^{\mathcal O\left((\log^{\circledast 4} T)^2\right)}
        \leq 2^{\mathcal O\left( \log \log \log T\right)}
        \leq \left(\log \log T \right)^{\mathcal O(1)}.
    \]
    We thus conclude that
    \begin{align}
        L_{\synclock} 
         &\leq \gamma_1^{\tau} \prod_{i=1}^{\tau} \ell_i L_1 
        \leq \mathcal O\left(\log \log \log T\right) \cdot \ell_1 \ell_2 \ell_3^{\tau} \cdot \mathcal O(\log T \log n)\\
        &\leq  \mathcal O\left(\log \log \log T\right) 
            \cdot \mathcal O\left(\log T\right) 
            \cdot \mathcal O\left(\log \log T\right) 
            \cdot \mathcal O\left(\log \log T \right)^{\mathcal O(1)} 
            \cdot \mathcal O(\log T \log n)\\
        &\leq  \log^2 T \log n \cdot  \left(\log \log T\right)^{\mathcal O(1)}.
    \end{align}
    The total slowdown with respect to \textsc{Syn-Simple}\xspace corresponds to 
    $\prod_{i=1}^\tau \ell_i = \tilde{\mathcal O}(\log T)$. Hence the clock\xspace produced by the emulation is incremented every $\tilde{\mathcal O}(\log T)$ rounds.
    In other words we obtain a clock\xspace modulo $T\cdot f(T)$ for some function $f$.
    But using Remark \ref{rem:counters} we can still view this as a clock\xspace modulo $T$.
\hspace{\stretch{1}$\square$}


\subsection{Extension to general $T$ and running time improvement.}\label{sub:powerof}

In this subsection we aim to get rid of the assumption that $T$ is a power of $2$ in Lemma \ref{lem:threebits}, and also reduce the running time of our protocol to $\tilde{\mathcal O}\left(\log n \log T\right)$, proving Theorem \ref{thm:main}.

\begin{pseudocode}[!ht]
    \textbf{\textsc{Syn-Clock}\xspace protocol}

    \smallskip
    \textsc{Memory:}
    Each agent $u$ stores a clock\xspace $C'(u)$ which runs modulo $T' \gg \gamma
    \log n \log T$. Each agent $u$ also stores a variable $Q$ which is
    incremented only once every $T'$ rounds and runs modulo $T$.

    \smallskip
    \textsc{Message:}
    Each agent $u$ displays $4$ bits.
    On the first $3$ bits, protocol \textsc{Syn-Intermediate}\xspace is applied to synchronize $C'$. 
    The $4$-th bit $b(u)$ is the
    bit with index $(\lfloor \frac{C'(u)}{\gamma\log n} \rfloor \mod \lceil
    \log T \rceil )$ of $Q(u)$.

    \smallskip
    \begin{description}
        \item[1] $u$ samples two agents $u_1$ and $u_2$.
        \item[2] $u$ updates $b(u)$ with the majority of $b(u)$, $b(u_1)$ and $b(u_2)$.
        \item[3] If $C'=0$, increment $Q$ by one unit modulo $T$.
    \end{description}

    \smallskip
    \textsc{Output:} 
    The clock\xspace modulo $T$ is obtained as $ C := \left(C'+ Q \cdot T'\right) \mod T$
    %
    \caption{The protocol $4$-bit \textsc{Syn-Clock}\xspace, executed by each agent $u$.}
    \label{alg:synclock}
\end{pseudocode}


\proofof{Theorem \ref{thm:main}}
    %
    From Lemma \ref{lem:threebits}, we know that 
    \textsc{Syn-Intermediate}\xspace synchronizes clocks\xspace modulo $T$ in time $ \tilde{\mathcal O}\left(\log^2 T \log n\right)$ using only $3$-bit messages, provided that $T$ is a power of 2. 
    %
    While protocol \textsc{Syn-Intermediate}\xspace emulates protocol \textsc{Syn-Simple}\xspace, it displays the first bit of the message of \textsc{Syn-Simple}\xspace only once every $\tilde{\mathcal O}\left(\log T\right)$ rounds. Of course, it would be more efficient to display it $\mathcal O\left(\log n\right)$ times in a row, so that \textsc{maj-consensus}\xspace would make every agent agree on this bit, and then move to agreeing on the second bit, and so on.
    %
    To achieve this, as in the proof of \textsc{Syn-Simple}\xspace, we can view a clock\xspace modulo $T$, say $Q$, as written on $\log T $ bits. If agents already possess a ``small'' counter modulo $T' := \mathcal O\left(\log T \log n\right)$ they can use it to display the first bit for $\mathcal O\left(\log n\right)$ rounds, then the second one for  $\mathcal O\left(\log n\right)$ rounds, and so on until each one of the $\lceil \log T \rceil$ bits of $T$ has been synchronized. 
    %
    This would synchronize all bits of the desired clock\xspace within $\mathcal O\left(\log T \log n\right)$ rounds, w.h.p., while being very economical in terms of message length, since only $1$ bit is displayed at any time.

    Therefore,  we can  use Lemma \ref{lem:threebits} to synchronize a counter modulo 
    $\mathcal O\left(\log T \log n \right)$ in  $\tilde \mathcal O ((\log \log T)^2\log n )$ rounds,
    using $3$ bits per message. Then, we can use a fourth bit to run \textsc{maj-consensus}\xspace on each of the $\log T$ bits of $Q$ for $\mathcal O(\log n)$ consecutive rounds, for a total running time of $\mathcal O(\log T \log n)$ rounds. At this point, an application of the \corelem\xspace would give us a protocol with running time $\mathcal O(\log T \log n)$ using $3$-bit messages. However, perhaps surprisingly, a similar strategy enables us to synchronize a clock modulo any integer (not necessarily a power of $2$). 
    %
   
   
   

    Let us assume that $T\in \NN$ is an arbitrary integer. Let $\gamma \log n$ be an upper bound on the convergence time of \textsc{maj-consensus}\xspace which guarantees a correct consensus with probability at least $1-n^{-2}$, for some constant $\gamma$ large enough \cite{DGM11}. Let $T'$ be the smallest power of $2$ bigger than $\log T \cdot \left(\const \log n + \const \log \log T\right)$.
    %
    By Lemma \ref{lem:threebits}, using $3$ bits, the agents can build a synchronized clock\xspace $C'$ running modulo $T'$ in time $\tilde \mathcal O ((\log \log T)^2\log n )$. The other main ingredient in this construction is another clock\xspace $Q_{T'}$ which is incremented once every $T'$ rounds and runs modulo $T$. 
    %
    The desired clock modulo $T$, which we denote $C$, is obtained by
    \begin{align}
        C := \left(C' + Q_{T'} \cdot T' \right)\mod T.
    \end{align}
    It is easy to check, given the definitions of $C'$ and $Q_{T'}$ that this choice indeed produces a clock modulo $T$.
   
   

    It remains to show how the clock\xspace $Q_{T'}$ modulo $T$ is synchronized. 
    On a first glance, it may seem as if we did not simplify the problem since $Q$ is a clock modulo $T$ itself. However, the difference between $Q_{T'}$ and a regular clock\xspace modulo $T$ is that $Q_{T'}$ is incremented only once every $T'$ rounds. This is exploited as follows.

    The counter $Q_{T'}$ is written on $\lceil \log T\rceil$ internal bits. We show how to synchronize $Q_{T'}$ using a 4-th bit in the messages, similarly to the aforementioned strategy to synchronize $Q$; we later show how to remove this assumption using the \corelem\xspace. Let us call a loop of $C'$ modulo $T'$ an \emph{epoch}. The rounds of an epoch are divided in phases of equal length $\const \log n + \const \log \log T$ (the remaining $T' \mod (\const \log n + \const \log \log T)$ rounds are just ignored). 
    %
    The clock $C'$ determines which bit from $Q_{T'}$ to display. The first bit of $Q_{T'}$ is displayed during the first phase, then the second one is displayed during the second phase, and so on. By Theorem \ref{thm:doerr}, the length of each phase guarantees that consensus is achieved on each bit of $Q_{T'}$ via%
    \footnote{Observe that, once clock\xspace $C'$ is synchronized, the bits of
        $Q_{T'}$ do not change for each agent during each subphase. Thus, we
        may replace \textsc{maj-consensus}\xspace by the \textsc{Min} protocol where on each round of
        subphase $i$ each agent $u$ pulls another agent $v$ u.a.r. and updates her
        $i$-th bit of $Q$ to the minimum between her current $i$-th bit of $Q$ and the
        one of $v$. However, for simplicity's sake, we reuse the already introduced
        \textsc{maj-consensus}\xspace protocol.}
    \textsc{maj-consensus}\xspace w.h.p. 
    %
    More precisely, after the first bit has been displayed for $\const \log n + \const \log \log T$ rounds, all agents agree on it with probability%
    \footnote{From Theorem \ref{thm:doerr}, we have that after $\gamma \log n$ rounds, with $\gamma$ large enough, the probability that consensus has not been reached is smaller than $ \frac{1}{n^2}$. Thus, after $N \cdot \gamma \log n$ rounds, the probability that consensus has not been reached is smaller than $\frac{1}{n^{2N}}$. 
    If we choose $N \log n = \log n + \log \log T$, we thus get the claimed upper bound $\frac{1}{n^2 \log T}$.}
    $1 - \frac{1}{n^2 \log T}$, provided $\gamma$ is large enough. 
    %
    Thus, at the end of an epoch, agents agree on all $\lceil \log T \rceil$ bits of $Q_{T'}$ with probability greater than $(1-\frac{1}{n^2 \log T})^{\log T}\gg 1-\mathcal O(n^{-2})$.

    We have thus shown that, by the time $C'$ reaches its maximum value of $T'$, i.e. after one epoch, all agents agree on $Q_{T'}$ w.h.p. and then increment it jointly.
    From Lemma \ref{lem:threebits}, \textsc{Syn-Intermediate}\xspace takes $\tilde{\mathcal O}\left(\log^2 T' \log n\right) = \mathcal O\left((\log \log n + \log \log T)^2 \log n\right) = \mathcal O\left(\left((\log \log n)^2\log n + (\log \log T)^2 \log n\right)\right)$ rounds to synchronize a clock $C'$ modulo $T'$ w.h.p.
    %
    Together with the $\log T\left(\const \log n + \const \log \log T\right)$ rounds to agree on $Q_{T'}$ w.h.p., this implies that after $\log T \log n \cdot
    (\log \log T)^{\mathcal O(1)} \cdot (\log \log n)^{\mathcal O(1)}=\tilde{\mathcal O}\left(\log T \log n\right)$ rounds the clocks $C$ are all synchronized w.h.p.

    Finally, we show how to get rid of the extra $4$-th bit to achieve agreement on $Q_{T'}$. Observe that, once $C'$ is synchronized, this bit is used in a self-stabilizing way. Thus, since \textsc{Syn-Intermediate}\xspace has the bitwise-independence\xspace property, using Lemma \ref{lem:ipfact}, the protocol we described above possesses the bitwise-independence\xspace property too. 
    %
    By using the \corelem\xspace we can thus reduce the message size from $4$ bits to $\lceil \log 4 \rceil +1 = 3$ bits, while only incurring a constant multiplicative loss in the running time. 
    %
    The  clock\xspace we obtain, counts modulo $T$ but is incremented every $4$ rounds only. It follows from Remark \ref{rem:counters} that we may still view this as a clock\xspace modulo $T$.
\hspace{\stretch{1}$\square$}

\begin{remark}[Internal memory space]
The internal memory space needed to implement our protocols \textsc{Syn-Simple}\xspace, \textsc{Syn-Intermediate}\xspace, and \textsc{Syn-Clock}\xspace is close to $\log T$ in all cases:
protocol \textsc{Syn-Simple}\xspace uses one counter written on $\log T$ bits, \textsc{Syn-Intermediate}\xspace needs internal memory of size 
\begin{equation}
   \log T + \mathcal O\left(\log \log T+ \log \log \log T + \ldots\right) \leq  \log T (1+o(1)),
\end{equation}
and the internal memory requirement of  \textsc{Syn-Clock}\xspace is of order $\log T + \log \log n$. 
\end{remark}


\section{Majority\xspace Bit Dissemination\xspace with a Clock}\label{sec:majority}

In this section we assume that agents are equipped with a synchronized clock\xspace $C$ modulo $\gamma \log n$ for some big enough constant $\gamma>0$. In the previous section we showed how to establish such a synchronized clock in $\tilde{\mathcal O}(\log n)$ time and using 3-bit messages.
We have already seen in Section \ref{sec:technical} how to solve the Bit Dissemination\xspace problem (when we are promised to have a single source agent) assuming such synchronized clocks\xspace, by paying an extra bit in the message size and an $\mathcal O(\log n)$ additive factor in the running time. 
This section is dedicated to showing that, in fact, the  more general Majority\xspace Bit Dissemination\xspace problem can be solved with the same time complexity and using 3-bit messages, proving Theorem \ref{thm:multi}.
 

In Section \ref{sec:spread}, we describe and analyze protocol \textsc{Syn-Phase-Spread}\xspace, which solves
Majority\xspace Bit Dissemination\xspace
by paying only a $\mathcal O(\log n)$ additive overhead in the running time w.r.t. Clock Synchronization\xspace. 
For clarity's sake, we first assume that the protocol is using $4$ bits (i.e. 1 additional bit over the $3$ bits used for Clock Synchronization\xspace), and we later show how to decrease the number of bits back to 3 in Section \ref{sub:proofofmulti}, by applying the \corelem\xspace. 

The main idea behind the $3(+1)$-bit protocol, called
\textsc{Syn-Phase-Spread}\xspace, is to make the sources' input bits\xspace disseminate on the system in a way
that preserves the initial ratio $\frac{k_1}{k_0}$ between the
number of sources supporting the majority and minority input bit\xspace. This is
achieved by dividing the dissemination process in phases, similarly to the main
protocol in \cite{OHK14} which was designed to solve the Bit Dissemination\xspace problem in
a variant of the $\mathcal{PUSH}$ model in which messages are affected by noise. The
phases induces a spreading process which allows to leverage on the
concentration property of the Chernoff bounds, preserving the aforementioned
ratio. While, on an intuitive level, the role of noisy messages in the model
considered in \cite{OHK14} may be related to the presence of sources having
conflicting opinion in our setting, we remark that our protocol and its
analysis depart from those of \cite{OHK14} on several key points: while the
protocol in \cite{OHK14} needs to know the the noise parameter, \textsc{Syn-Phase-Spread}\xspace do not
assume any knowledge about the number of different sources, and our analysis do
not require to control the growth of the number of speaking agents from above%
\footnote{To get such upper bound, the analysis in \cite{OHK14} leveraged on the property that in the $\mathcal{PUSH}$ model the number of agents getting a certain message can be upper bounded by the number of agent sending such message, which is not the case for the passive communication of the $\mathcal{PULL}$ model.}.

In order to perform such spreading process with 1 bit only, the protocol in \cite{OHK14} leverages on the fact that in the $\mathcal{PUSH}$ model agents can choose {\em when to speak}, i.e. whether to send a message or not. To emulate
this property in the $\mathcal{PULL}$ model, we use the parity of the clock $C$: on
odd rounds agents willing to ``send'' a  $0$ display $0$, while others display $1$ and conversely on even rounds. Rounds are then grouped by two, so $2$ rounds in the $\mathcal{PULL}$ model correspond to $1$ round in the $\mathcal{PUSH}$ version. 


\subsection{Protocol \textsc{Syn-Phase-Spread}\xspace}\label{sec:spread}
 
\global\long\def\textsc{Com-Spread}{\textsc{Com-Spread}}

\global\long\def\gamma_{phase}{\gamma_{phase}}
\global\long\defC{C}
\global\long\def2\lceil \gamma_{phase} \log n\rceil + \gamma_{phase}\lceil 2\log n \rceil{2\lceil \gamma_{phase} \log n\rceil + \gamma_{phase}\lceil 2\log n \rceil}

\global\long\def\gamma_{phase}{\gamma_{phase}}
\global\long\def\constphase{\gamma_{phase}}
\global\long\def\gamma_{phase}{\gamma_{phase}}

\global\long\def\gamma_{trial}{\gamma_{trial}}

In this section we describe protocol \textsc{Syn-Phase-Spread}\xspace. As mentioned above, for clarity's sake we assume that \textsc{Syn-Phase-Spread}\xspace uses $4$-bit messages, and we show how to remove this assumption in Section \ref{sub:proofofmulti}.
Three of such bits are devoted to the execution $\textsc{Syn-Clock}\xspace$, in order to synchronize a clock\xspace $C$ modulo $2\lceil \gamma_{phase} \log n\rceil + \gamma_{phase}\lceil 2\log n \rceil$
for some constant $\gamma_{phase}$ large enough.
Throughout this section we assume, thanks to Theorem \ref{thm:main}, that $C$ has already been synchronized, which happens after $\tilde{\mathcal O} (\log n)$ rounds from the start of the protocol. In Section \ref{sec:majprot}, we present a protocol \textsc{Phase-Spread}\xspace solving Majority\xspace Bit Dissemination\xspace assuming agents already share a common clock.

\subsubsection{Protocol \textsc{Phase-Spread}\xspace}
\label{sec:majprot}
Let $\gamma_{phase}$ be a constant to be set later. 
Protocol
\textsc{Phase-Spread}\xspace is executed periodically over periods of length $2\lceil \gamma_{phase} \log n\rceil + \gamma_{phase}\lceil 2\log n \rceil$, given by a clock\xspace $C$. One run of length $2\lceil \gamma_{phase} \log n\rceil + \gamma_{phase}\lceil 2\log n \rceil$ is divided in $2+\lceil 2\log n \rceil$ phases, the first
and the last ones lasting $\lceil \gamma_{phase}\log n \rceil$ rounds, all the other
$\lceil 2\log n \rceil$ phases lasting $\gamma_{phase}$ rounds. The first phase is called \emph{boosting},
the last one is called \emph{polling}, and all the intermediate ones
are called \emph{spreading}.
For technical convenience, in \textsc{Phase-Spread}\xspace agents disregard the messages they get as their second pull\footnote{In other words, \textsc{Phase-Spread}\xspace works in the $\mathcal{PULL}(1)$ model.}.

During the boosting and the spreading phases, as we already explained in the introduction of this section, we make use of the parity of time to emulate the ability to actively send a message or not to communicate anything as in the $\mathcal{PUSH}$ model%
\footnote{Of course, agents are still not able to control who sees/contacts them.}
(in the first case we say that the agent is \emph{speaking}, in the second case we say that the agent is \emph{silent}).
This induces a factor $2$ slowdown which we henceforth  omit for simplicity. 
 

\global\long\deff_{1}{f_{1}}
\global\long\deff_{0}{f_{0}}


At the beginning of the boosting, each non-source agent $u$ is
silent. 
During the boosting and during
each spreading phase, each silent agent pulls until she sees a speaking
agent. When a silent agent $u$ sees a speaking agent $v$,
$u$ memorizes $b_{1}\left(v\right)$ but remains silent until
the end of the phase; at the end of the current phase, $u$ starts speaking and sets $b_{1}\left(u\right)=b_{1}\left(v\right)$.
The bit $b_{1}$ is then never modified until the clock\xspace $C$ reaches $0$ again.
Then, during the
polling phase, each agent $u$ counts how many agents with $b_{1}=1$
and how many with $b_{1}=0$ she sees.
At the end of the phase, each agent $u$ sets their output bit to the most frequent value of $b_{1}$ observed during the
polling phase.
We want to show that, for all agents, the latter is w.h.p. $b_{maj}$ (the most frequent initial opinion\xspace among sources).

\begin{pseudocode}[!ht]
    \textbf{\textsc{Phase-Spread}\xspace protocol}

    \smallskip
    \begin{description}
        \item[1] If $u$ is not speaking and the current phase is either the boosting or 
            the spreading one, $u$ does the following:
            \item[2] \hspace{.2cm}$|$\hspace{.2cm} $u$ observes a random agent $v$. 
            \item[3] \hspace{.2cm}$|$\hspace{.2cm} If $v$ is speaking, 
                $u$ sets $b_{1}(u)$ equal to $b_{1}(v)$,\\
                \-\hspace{.5cm} and $u$ will be speaking from the next phase.
            \item[4] \hspace{.2cm}$|$\hspace{.2cm} $u$ sets $c_0$ and $c_1$ equal to $0$.
        \item[5] If the current phase is polling:
            \item[6] \hspace{.2cm}$|$\hspace{.2cm} $u$ observes a random agent $v$. 
            \item[7] \hspace{.2cm}$|$\hspace{.2cm} If $b_1(v)=1$, $u$ increments $c_1$, 
                otherwise increment $c_0$. 
        \item[8] $u$ outputs $1$ if and only if $c_1 > c_0$.
    \end{description}
    %
    \caption{The protocol \textsc{Phase-Spread}\xspace, executed by each agent $u$.}
    \label{alg:majprot}
\end{pseudocode}

\subsubsection{Analysis}
We prove that at the end of the last spreading phase w.h.p.
all agents are speaking and each agent has $b_{1}=1$ with probability
$\frac{1}{2}+\epsilon_{end}$ for some positive constant $\epsilon_{end}=\epsilon_{end}\left(\gamma_{phase}, \epsilon\right)$ (where the dependency in $\gamma_{phase}$ is monotonically increasing),
$b_{1}=0$ otherwise. From the Chernoff bound (Corollary \ref{cor:cb})
and the union bound, this implies that when $\gamma_{phase}>\frac{8}{\epsilon_{end}}$
at the end of the polling phase w.h.p. each agent learns
$b_{maj}$. 

Without loss of generality, let $b_{maj}=1$, i.e. $k_1>k_0$. 

The analysis is divided in the following lemmas.
\begin{lemma}
    \label{lem:boosting_conc}
    At the end of the boosting phase it holds
    w.h.p.
    %
    \begin{align}
        \sizeblack^{\left(1\right)}+\sizewhite^{\left(1\right)} 
        & \geq\left(k_1+k_0\right)\frac {\gamma_{phase}}3 \log
                n\cdot\mbox{\textbf{1}}_{\left\{
                    k_1+k_0<\frac{n}{2\gamma_{phase} \log n}\right\} }
            +\left(n\left(1-\frac{1}{\sqrt{e}}\right) 
            +\frac{1}{\sqrt{e}}\left(k_1+k_0\right)-\sqrt{n\log
                n}\right)\nonumber \\
         & \qquad \cdot\mbox{\textbf{1}}_{\left\{
             \frac{n}{2\gamma_{phase}}\leqk_1+k_0\leq n-2\sqrt{n\log
             n}\right\} }
         \qquad +n\mbox{\textbf{1}}_{\left\{
                 k_1+k_0>n-2\sqrt{n\log n}\right\}
             },\label{eq:boost_spread}\\
        \frac{\sizeblack^{\left(1\right)}}{\sizewhite^{\left(1\right)}} 
             &\geq\frac{k_1}{k_0}\left(1-\sqrt{\frac{9}{\newconstboostk_0}}\right).
        \label{eq:boost_bias}
    \end{align}
    \global\long\def\mathbb{E}{\mathbb{E}}
\end{lemma}

\begin{proof
    First, we prove \eqref{eq:boost_spread}. By using Fact \ref{fact:exp_ineq},
    we have
    \begin{align}
        \mathbb{E}\left[\sizeblack^{\left(1\right)}+k_0^{\left(1\right)}\right]
        & =k_1+k_0+\left(n-k_1-k_0\right)
            \left(1-\left(1-\frac{k_1+k_0}{n}\right)^{\gamma_{phase}
            \log n}\right)\nonumber \\
        & \qquad\geqk_1+k_0+\left(n-k_1-k_0\right)
            \left(1
                -e^{-\frac{k_1+k_0}{n}\gamma_{phase} \log n}\right).
        \label{eq:boost_before_cases}
    \end{align}
    We distinguish three cases.

    \textbf{Case $k_1+k_0<\frac{n}{2\gamma_{phase}\log n}$.}
    By using Fact \ref{fact:exp_ineq} again, from \eqref{eq:boost_before_cases}
    we get
    \begin{align}
        \mathbb{E}\left[\sizeblack^{\left(1\right)}+k_0^{\left(1\right)}\right] 
        & \geqk_1+k_0+\left(n-k_1-k_0\right)
            \left(1-e^{-\frac{k_1+k_0}{n}\gamma_{phase}\log
            n}\right)\nonumber \\
        & \geqk_1+k_0+\left(n-k_1-k_0\right)
            \frac{\frac{k_1+k_0}{n}\gamma_{phase}\log n}
                {1+\frac{k_1+k_0}{n}\gamma_{phase}\log n}\nonumber \\
        & \geqk_1+k_0+
            \left(n-k_1-k_0\right)
            {\frac{k_1+k_0}{n}\frac{\gamma_{phase}}2 \log n}\nonumber \\
        & \geqk_1+k_0+\left(1-\frac{k_1+k_0}{2n}\right)
            \left(k_1+k_0\right)\frac{\gamma_{phase}}2
        \log n\nonumber\\
        &\geq 
          \left(k_1+k_0\right)
          \left(1+\left(1-\frac{1}{4\gamma_{phase}\log n}\right)\frac{\gamma_{phase}}2\log n\right)\\
        &\geq \left(k_1+k_0\right)\frac{\gamma_{phase}}2 \log n.
        \label{eq:exp_spread}
    \end{align}
    From the Chernoff bound (Lemma \ref{thm:gen_cb}), we thus get that
    w.h.p. 
    \[
    \sizeblack^{\left(1\right)}+k_0^{\left(1\right)}\geq  \left(k_1+k_0\right)\frac{\gamma_{phase}}{3} \log n.
    \]

    \textbf{Case $\frac{n}{2\gamma_{phase}\log n} \leq k_1+k_0\leq n-2\sqrt{n\log n}$.}
    From \eqref{eq:boost_before_cases}, we have
    \begin{align}
        \mathbb{E}\left[\sizeblack^{\left(1\right)}+k_0^{\left(1\right)}\right] 
        & \geqk_1+k_0+\left(n-k_1-k_0\right)
            \left(1-e^{-\frac{k_1+k_0}{n}\gamma_{phase}}\right)\\
        & \geqk_1+k_0+\left(n-k_1-k_0\right)
            \left(1-\frac{1}{\sqrt{e}}\right)\\
        &\geq n\left(1-\frac{1}{\sqrt{e}}\right)+\frac{k_1+k_0}{\sqrt{e}}.
    \end{align}
    From the Chernoff bound (Lemma \ref{thm:gen_cb}), we thus get that
    w.h.p. 
    \[
    \sizeblack^{\left(1\right)}+k_0^{\left(1\right)}\geq n\left(1-\frac{1}{\sqrt{e}}\right)+\frac{k_1+k_0}{\sqrt{e}}-\sqrt{n\log n}.
    \]

    \textbf{Case $\sizeblack^{\left(1\right)}+\sizewhite^{\left(1\right)}>n-2\sqrt{n\log n}$.} The probability
    that a silent agent does not observe a speaking one is 
    \[
    \left(\frac{n-k_1-k_0}{n}\right)^{\gamma_{phase} \log n}\leq 
    \left(\frac{4\log n}{n}\right)^{\frac{1}{2}\gamma_{phase} \log n},
    \]
    hence by a simple union bound it follows that w.h.p.
    all agents are speaking. 

    Now, we prove \eqref{eq:boost_bias}. As before, we have two cases.
    The first case, $\frac{k_1}{k_0}\geq\frac{n}{2\gamma_{phase}\log n}$,
    is a simple consequence of the Chernoff bound (Lemma \ref{thm:gen_cb}). 

    \global\long\defS_{boost}{S_{boost}}


    In the second case, $\frac{k_1}{k_0}<\frac{n}{2\gamma_{phase}\log n}$,
    let us consider the set of agents $S_{boost}$ that start speaking
    at the end of the boosting, i.e. that observe a speaking agent during
    the phase. Observe that $\left|S_{boost}\right|=\sizeblack^{\left(1\right)}-k_1+k_0^{\left(1\right)}-k_0$.
    The probability that an agent in $S_{boost}$ observes an agent in
    $\mathcal{B}$ (resp. $\mathcal{W}$) is $\frac{k_1}{k_1+k_0}$
    (resp. $\frac{k_0}{k_1+k_0}$). Thus
    \begin{align}
    \mathbb{E}\left[\sizeblack^{\left(1\right)}\right] & =k_1+\frac{k_1}{k_1+k_0}\mathbb{E}\left[\left|S_{boost}\right|\right]\quad\mbox{and}\nonumber \\
    \mathbb{E}\left[k_0^{\left(1\right)}\right] & =k_0+\frac{k_0}{k_1+k_0}\mathbb{E}\left[\left|S_{boost}\right|\right].\label{eq:exp_white_boost}
    \end{align}
    In particular 
    \begin{equation}
      \frac{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]}{\mathbb{E}\left[k_0^{\left(1\right)}\right]}=\frac{k_1+\frac{k_1}{k_1+k_0}\mathbb{E}\left[\left|S_{boost}\right|\right]}{k_0+\frac{k_0}{k_1+k_0}\mathbb{E}\left[\left|S_{boost}\right|\right]}=\frac{k_1}{k_0},\label{eq:exp-ratio}  
    \end{equation}
    and from \eqref{eq:exp_spread} and \eqref{eq:exp_white_boost} we have
    \begin{align}
        \mathbb{E}\left[k_0^{\left(1\right)}\right]
        &\geq\frac{k_0}{k_1+k_0}\mathbb{E}\left[\left|S_{boost}\right|\right]\\
        & =\frac{k_0}{k_1+k_0}
            \left(\mathbb{E}\left[\sizeblack^{\left(1\right)}+k_0^{\left(1\right)}\right]
                -\left(k_1+k_0\right)\right)\\
        &\geq (1-o(1)) \frac{k_0}{k_1+k_0}\frac{\gamma_{phase}}{2}\left(k_1+k_0\right)\log n\\
        &= (1-o(1)) {k_0}\frac{\gamma_{phase}}{2} \log n,
        \label{eq:exp_white_boost_lower}
    \end{align}
    where the lower bound follows from the assumption $\frac{k_1}{k_0}<\frac{n}{2\gamma_{phase}\log n}$ and
    \eqref{eq:exp_spread}.
    %
    From \eqref{eq:exp_white_boost_lower} and the multiplicative form of the Chernoff bound (Corollary \ref{cor:cb}),
    we have that w.h.p. 
    \begin{align}
        & \sizeblack^{\left(1\right)}  \geq\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]-\sqrt{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]\log n}\quad\mbox{and}\\
        & \sizewhite^{\left(1\right)}  \leq\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]+\sqrt{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]\log n}.\label{eq:exp_white_boost_whp}
    \end{align}


    Thus, since \eqref{eq:exp_white_boost} implies $\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]\geq \mathbb{E}\left[\sizewhite^{\left(1\right)}\right]$, we have
    \begin{align}
         \frac{\sizeblack^{\left(1\right)}}{\sizewhite^{\left(1\right)}}  
         &   \geq\frac{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]-\sqrt{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]\log n}}
                {\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]+\sqrt{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]\log n}}\\
        & =\frac{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]}{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]}
            \cdot \frac{1-\sqrt{\frac{\log n}{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]}}}
                {1+\sqrt{\frac{\log n}{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]}}}\\
        &\geq\frac{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]}{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]}
            \cdot \left(1-\sqrt{\frac{\log n}{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]}}
                -\sqrt{\frac{\log n}{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]}}\right) \\
        & \geq\frac{\mathbb{E}\left[\sizeblack^{\left(1\right)}\right]}{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]}
            \cdot \left(1-2\sqrt{\frac{\log n}{\mathbb{E}\left[\sizewhite^{\left(1\right)}\right]}}\right) \\
        & =\frac{k_1}{k_0}
            \cdot\left(1-\sqrt{\frac{9}{k_0\gamma_{phase}}}\right),
        \label{eq:recurs_whp}
    \end{align}
    concluding the proof.
\end{proof}
\begin{lemma}
    At the end of the $i+1$th spreading phase, the following holds w.h.p.
    \begin{align}
        \sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}
        & \geq\left(\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\right) \frac{\constphase}3 \mbox{\textbf{1}}_{\left\{ \sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}<\frac{n}{2\gamma_{phase}}\right\} }
        +\left(n\left(1-\frac{1}{\sqrt{e}}\right)+\frac{1}{\sqrt{e}}
            \left(\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\right)-\sqrt{n\log n}\right)\nonumber \\
        & \qquad \qquad \cdot\mbox{\textbf{1}}_{\left\{ \frac{n}{2\gamma_{phase}}
            \leq\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\leq n-2\sqrt{n\log n}\right\} }
        +n\mbox{\textbf{1}}_{\left\{ \sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}>n-2\sqrt{n\log n}\right\} },
        \label{eq:increase_big}\\
         \frac{\sizeblack^{\left(i+1\right)}}{\sizewhite^{\left(i+1\right)}}
         &   \geq\frac{\sizeblack^{\left(i\right)}}{\sizewhite^{\left(i\right)}}\left(1- 4 \sqrt{\frac{\log n}
                {\gamma_{phase}\sizewhite^{\left(i\right)}}}\right).
        \label{eq:rel_bias}
    \end{align}
\end{lemma}
\begin{proof}
    The proof is almost the same as that of Lemma \ref{lem:boosting_conc}. Thus, 
    we here condense some analogous calculations.

    First, we prove \eqref{eq:increase_big}. By using Fact \ref{fact:exp_ineq},
    we have
    \begin{align}
        \mathbb{E}\left[\sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}\right]
       
       
         \geq\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}+\left(n-\sizeblack^{\left(i\right)}-\sizewhite^{\left(i\right)}\right)
            \left(1- e^{-\frac{\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}}{n}\gamma_{phase}}\right).
        \label{eq:boost_before_cases-1}
    \end{align}
    We distinguish three cases.

    \textbf{Case $\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}<\frac{n}{2\gamma_{phase}}$.} By using
    Fact \ref{fact:exp_ineq} again, from \eqref{eq:boost_before_cases-1}
    we get
    \begin{align}
        \mathbb{E}\left[\sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}\right]
       
       
       
       
       
        & \geq\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}+\left(n-\sizeblack^{\left(i\right)}-\sizewhite^{\left(i\right)}\right)\cdot
            \frac{\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}}{2n}\gamma_{phase}
       
       
       
       
        \geq \left(\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\right)\frac{\gamma_{phase}}2.
        \label{eq:exp_spread-1}
    \end{align}
    After the boosting phase, i.e. for $i\geq 1$, it follows from Lemma \ref{lem:boosting_conc}
    that $\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)} = \Omega\left( \gamma_{phase} \log n\right)$. From the Chernoff bound (Lemma \ref{thm:gen_cb}),
    if $\gamma_{phase}$ is chosen big enough, we thus get that
    w.h.p. 
    \[
    \sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}\geq\left(\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\right)\frac \gamma_{phase} 3.
    \]


    \textbf{Case $\frac{n}{2\gamma_{phase}}\leq\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\leq n-2\sqrt{n\log n}$.}
    From \eqref{eq:boost_before_cases-1}, we have
    \begin{align}
        \mathbb{E}\left[\left(\sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}\right)\right]
       
       
        & \geq\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}+\left(n-\sizeblack^{\left(i\right)}-\sizewhite^{\left(i\right)}\right)\left(1-\frac{1}{\sqrt{e}}\right)
        \geq n\left(1-\frac{1}{\sqrt{e}}\right)+\frac{1}{\sqrt{e}}\left(\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\right).
    \end{align}
    From the Chernoff bound (Lemma \ref{thm:gen_cb}), we thus get that
    w.h.p. 
    \[
    \sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}\geq n\left(1-\frac{1}{\sqrt{e}}\right)+\frac{1}{\sqrt{e}}\left(\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}\right)-\sqrt{n\log n}.
    \]


    \textbf{Case $\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}>n-2\sqrt{n\log n}$.} The probability
    that a silent agent does not observe a speaking one is 
    \[
        \left(\frac{n-\sizeblack^{\left(i\right)}-\sizewhite^{\left(i\right)}}{n}\right)^{\gamma_{phase}}\leq \left(\frac{4\log n}{n}\right)^{\frac{1}{2}\gamma_{phase}},
    \]
    %
    hence by a simple union bound it follows that w.h.p.
    all agents are speaking. 

    Now, we prove \eqref{eq:rel_bias}. 
    %
    As in the proof of \eqref{eq:boost_bias}, we have two cases. 
    %
    The first case, $\frac{k_1}{k_0}\geq\frac{n}{2\gamma_{phase}}$,
    is a simple consequence of the Chernoff bound (Lemma \ref{thm:gen_cb}). 
    %
    Otherwise, let us assume $\frac{k_1}{k_0}<\frac{n}{2\gamma_{phase}}$.
    %
    With an analogous argument to that
    for \eqref{eq:exp_white_boost} and \eqref{eq:exp-ratio} we can prove 
    \begin{equation}
        \frac{\mathbb{E}\left[\sizeblack^{\left(i+1\right)}\right]}{\mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right]}  =\frac{\sizeblack^{\left(i\right)}}{\sizewhite^{\left(i\right)}},\label{eq:expec_new_ratio}
    \end{equation}
    and
    \begin{align}
        & \mathbb{E}\left[\sizeblack^{\left(i+1\right)}\right] 
        = \sizeblack^{\left(i\right)} + \frac{\sizeblack^{\left(i\right)}}{\sizeblack^{\left(i\right)}+\sizeblack^{\left(i\right)}}
             \mathbb{E}\left[\sizeblack^{\left(i+1\right)}-\sizeblack^{\left(i\right)}+\sizewhite^{\left(i+1\right)}-\sizewhite^{\left(i\right)}\right],\\
        & \mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right]
        = \sizewhite^{\left(i\right)} + \frac{\sizewhite^{\left(i\right)}}{\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}}
            \mathbb{E}\left[\sizeblack^{\left(i+1\right)}-\sizeblack^{\left(i\right)}+\sizewhite^{\left(i+1\right)}-\sizewhite^{\left(i\right)}\right].
        \label{eq:min_exp_next_white}
    \end{align}
     As in \eqref{eq:exp_white_boost_whp}, from the multiplicative form
    of the Chernoff bound (Corollary \ref{cor:cb}) we have that w.h.p.
    \begin{align}
        & \sizeblack^{\left(i+1\right)}  \geq\mathbb{E}\left[\sizeblack^{\left(i+1\right)}\right]-\sqrt{\mathbb{E}\left[\sizeblack^{\left(i+1\right)}\right]\log n}\quad\mbox{and}\\
        & \sizewhite^{\left(i+1\right)}  \leq\mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right]+\sqrt{\mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right]\log n}.\label{eq:cb_newratios}
    \end{align}

    Thus, as in \eqref{eq:recurs_whp}, from \eqref{eq:cb_newratios} and \eqref{eq:expec_new_ratio}, we get
    \begin{align}
        \frac{\sizeblack^{\left(i+1\right)}}{\sizewhite^{\left(i+1\right)}}
        & \geq\frac{\mathbb{E}\left[\sizeblack^{\left(i+1\right)}\right]}{\mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right]}
            \cdot \left(1-2\sqrt{\frac{\log n}{\mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right]}}\right)
        \geq\frac{\sizeblack^{\left(i\right)}}{\sizewhite^{\left(i\right)}} 
            \cdot \left(1- 4\sqrt{\frac{\log n}{\gamma_{phase}\sizewhite^{\left(i\right)}}} \right),
    \end{align}
    where, as in \eqref{eq:exp_white_boost_lower}, in the last inequality we used that from \eqref{eq:exp_spread-1} and \eqref{eq:min_exp_next_white} it holds $ \mathbb{E}\left[\sizewhite^{\left(i+1\right)}\right] \geq \frac \newconstboost4 \sizewhite^{\left(i\right)}$. 
\end{proof}

From the previous two lemmas, we can derive the following corollary,
which concludes the proof. 
\begin{corollary}\label{cor:ultimate}
    If $k_1 \geq k_0 (1+\epsilon)$ for some constant
    $\epsilon>0$, then at the end of the last spreading phase it holds w.h.p.
    \begin{align}
        k_1^{\left(1+2\log n\right)} 
        & =n-k_0^{\left(1+2\log n\right)}
        \geqk_0^{\left(1+2\log n\right)}\left(1+\epsilon_{end}\right),
        \label{eq:full_opinion}
    \end{align}
    where 
    $\epsilon_{end}= \frac {\epsilon} 2 -\frac{4}{\sqrt{\gamma_{phase}}}$.
\end{corollary}
\begin{proof}
    We first show how the equality in \eqref{eq:full_opinion} follows from \eqref{eq:increase_big}. 
    When $\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}<\frac{n}{2\gamma_{phase}}$, equation 
    \eqref{eq:increase_big} shows that $\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}$ increases by multiplicative a factor 
    $\gamma_{phase}$ at the end of each spreading phase. 
    When $\frac{n}{2\gamma_{phase}} \leq \sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)} \leq n-2\sqrt{n\log n}$
    equation \eqref{eq:increase_big} shows that
    \begin{align}
        n- \sizeblack^{\left(i+1\right)} -\sizewhite^{\left(i+1\right)} 
        & \leq \frac{ n-\sizeblack^{\left(i\right)}-\sizewhite^{\left(i\right)} }{\sqrt{e}} - \sqrt{n \log n} 
        \leq \frac{n-\sizeblack^{\left(i\right)}-\sizewhite^{\left(i\right)} }{\sqrt{e}}.
    \end{align}
    Hence the number of silent agents decreases by a factor $\sqrt{e}$ after each spreading phase.
    Lastly, when
    $\sizeblack^{\left(i\right)}+\sizewhite^{\left(i\right)}>n-2\sqrt{n\log n}$, after one more spreading phase, a simple application of the  union bound shows that $\sizeblack^{\left(i+1\right)}+\sizewhite^{\left(i+1\right)}$ is equal to $n$ w.h.p. As a consequence,
    if $\gamma_{phase}$ is big enough, %
    after less than
    $ 1+ 2\log n $
    spreading phases w.h.p it holds that
    $
    k_1^{\left(1+2\log n\right)} =n-k_0^{\left(1+2\log n\right)}
    $. 

    The inequality in \eqref{eq:full_opinion} can be derived from \eqref{eq:rel_bias}, as
    follows. From \eqref{eq:boost_bias} and \eqref{eq:rel_bias} we have
    \begin{align}
        & \frac{k_1^{\left(1+2\log n\right)}}{k_0^{\left(1+2\log n\right)}} 
        \geq\frac{k_1}{k_0}
            \left(1-\sqrt{\frac{9}{\newconstboostk_0}}\right)
            \prod_{i=2}^{1+2\log n}\left(1-\sqrt{\frac{16\log n}{\gamma_{phase}\sizewhite^{\left(i\right)}}}\right).
        \label{eq:final_ratio}
    \end{align}
    We can estimate the product as
    \begin{align}
         \prod_{i=2}^{1+2\log n}\left(1-\sqrt{\frac{16\log n}{\gamma_{phase}\sizewhite^{\left(i\right)}}}\right)
        &\geq\exp\left(- 4 \sum_{i=2}^{1+2\log n}\frac{1}
            {\left(\sqrt{\gamma_{phase}}\right)^{i}}\right),\\
        & \geq\exp\left\{ 4 \left(1+\frac{1}{\sqrt{\gamma_{phase}}}
            -\frac{1-\left(\gamma_{phase}\right)^{-\frac{2+2\log n}{2}}}
                {1-\left(\gamma_{phase}\right)^{-\frac{1}{2}}}\right)\right\}\\
        & \geq\exp\left\{- 4 \left(\frac{1}{\gamma_{phase}-\sqrt{\gamma_{phase}}}
            -n^{-\frac{2\log\gamma_{phase}}{2}}\right)\right\}\\
        & \geq\left(1-\frac{5}{\gamma_{phase}}\right),
        \label{eq:prod_lower}
    \end{align}
    where in the first and last inequality we used that $1-x\geq e^{-\frac{x}{1-x}}$
    if $\left|x\right|<1$.

    Finally, from \eqref{eq:final_ratio} and \eqref{eq:prod_lower} we
    get
    \begin{align}
        \frac{k_1^{\left(1+2\log n\right)}}{k_0^{\left(1+2\log n\right)}}
        & \geq\frac{k_1}{k_0}
            \left(1-\sqrt{\frac{9}{\newconstboostk_0}}\right)
            \left(1-\frac{5}{\gamma_{phase}}\right)
        \geq\frac{k_1}{k_0}\left(1-\frac{4}{\sqrt{\gamma_{phase}}}\right),
    \end{align}
    which, together with the hypothesis 
    $\frac{k_1}{k_0} \geq 1+ \epsilon$,
    concludes the proof.
\end{proof}

\subsection{Proof of Theorem \ref{thm:multi}}\label{sub:proofofmulti}


\begin{proof}
    From Corollary \ref{cor:ultimate}, it follows that at the end of the last spreading phase, all agents have been informed. 
    After the last spreading phase, during the polling phase, each agent samples $\gamma_{phase} \log n$ opinions from the population\xspace and then adopts the majority of these as her output bit. 
    %
    Thus, \eqref{eq:full_opinion} ensures that
    each sample 
    holds the correct opinion with probability
    $ \geq \frac{1}{2}+ \epsilon_{end}$. Hence, by the Chernoff bound and a union bound, if $\gamma_{phase}$ is big enough then the majority of the $\gamma_{phase} \log n$ samples corresponds to the correct value for all the $n$ agents w.h.p.

    The protocol obtained so far solves Majority\xspace Bit Dissemination\xspace, but it does it using $4$ bits per message rather than $3$. Indeed, synchronizing a clock using \textsc{Syn-Clock}\xspace takes $3$ bits, and we use an extra bit to execute \textsc{Phase-Spread}\xspace described in Section \ref{sec:majprot}.
    %
    However, the protocol \textsc{Syn-Phase-Spread}\xspace has the bitwise-independence\xspace property. This follows from Lemma \ref{lem:ipfact} with \textsc{Syn-Generic}\xspace$=$\textsc{Syn-Clock}\xspace, \textsc{P}\xspace$=$\textsc{Phase-Spread}\xspace, \textsc{Syn-P}\xspace$=$\textsc{Syn-Phase-Spread}\xspace, together with the observation that \textsc{Phase-Spread}\xspace is self-stabilizing.
    %
    %
    We can thus reduce the message length of \textsc{Syn-Phase-Spread}\xspace  to $3$ bits using again the \corelem\xspace, with a time overhead of a factor $4$ only.
\end{proof}


\section{Conclusion and Open Problems}

This paper deals with  the construction of protocols in highly congested
stochastic interaction patterns. Corresponding challenges are particularly
evident when it is difficult to guarantee synchronization, which seems to be
essential for emulating a typical protocol that relies on many bits per message
with a protocol that uses fewer bits. Our paper shows that in the $\mathcal{PULL}$
model, if a self-stabilizing protocol satisfies the bitwise-independence\xspace property then
it can be emulated with only 3 bits per message. Using this rather general
transformer, we solve the self-stabilizing  Clock-Synchronization and Majority\xspace
Bit Dissemination\xspace problems in almost-logarithmic time and using only $3$ bits per
message. It remains an open problem whether the message size of either one of
these problems can be further reduced while keeping the running time
polylogarithmic. 

In particular, even for the self-stabilizing Bit Dissemination\xspace problem (with a single
source) it remains open whether there exists a polylogarithmic protocol that
uses a single bit per interaction. 
In fact, we investigated several candidate protocols which seem promising in
experimental simulation, but appear to be out of reach of current techniques
for analysing randomly-interacting agent systems in a self-stabilizing context. 
Let us informally present one of them, called \textsc{BFS}\footnote{A similar
protocol was suggested during discussions with Bernhard Haeupler.}.
Let $\ell$,$ k\in \NN$ be two parameters, say of order $O(\log n)$. Agents can
be in $3$ states: \emph{boosting}, \emph{frozen} or \emph{sensitive}. 
Boosting agents behave as in the \textsc{maj-consensus}\xspace protocol: they apply the majority rule
to the $2$ values they see in a given round and make it into their opinion for
the next round. They also keep a counter $T$. If they have seen only agents of
a given color $b$ for $\ell $ rounds, they become sensitive to the opposite
value.
$b$-sensitive agents turn into frozen-$b$ agents if they see value $b$.
$b$-frozen agents keep the value $b$ for $k$ rounds before becoming boosters again.
Intuitively what we expect is that, from every configuration, at some point
almost all agents would be in the {boosting} state. Then, the boosting behavior
would lead the agents to converge to a value $b$ (which depends on the initial
conditions). Most agents would then become sensitive to $1-b$. If the source
has opinion $1-b$ then there should be a ``switch'' from $b$ to $1-b$. The
``frozen'' period is meant to allow for some delay in the times at which agents
become sensitive, and then flip their opinion. 


\medskip
{ {\paragraph{Acknowledgments:} The problem of self-stabilizing Bit Dissemination\xspace was introduced through discussions with Ofer Feinerman. The authors are also thankful for Omer Angel, Bernhard Haeupler, Parag Chordia, Iordanis Kerenidis,  
Fabian Kuhn, Uri Feige, and Uri Zwick for helpful discussions regarding that problem.  The authors also thank Michele Borassi for his helpful suggestions regarding the Clock Synchronization problem.
}}

\bibliographystyle{abbrv}
