In a previous note (arXiv:1712.01367 [cs.DC]) , we observed a safety violation in Zyzzyva and a liveness violation in FaB. In this manuscript, we sketch fixes to both. The same view-change core is applied in the two schemes, and additionally, applied to combine them and create a single, enhanced scheme that has the benefits of both approaches.
Broadcasting and gossiping are fundamental communication tasks in networks. In broadcasting,one node of a network has a message that must be learned by all other nodes. In gossiping, every node has a (possibly different) message, and all messages must be learned by all nodes. We study these well-researched tasks in a very weak communication model, called the {\em beeping model}. Communication proceeds in synchronous rounds. In each round, a node can either listen, i.e., stay silent, or beep, i.e., emit a signal. A node hears a beep in a round, if it listens in this round and if one or more adjacent nodes beep in this round. All nodes have different labels from the set $\{0,\dots , L-1\}$. Our aim is to provide fast deterministic algorithms for broadcasting and gossiping in the beeping model. Let $N$ be an upper bound on the size of the network and $D$ its diameter. Let $m$ be the size of the message in broadcasting, and $M$ an upper bound on the size of all input messages in gossiping. For the task of broadcasting we give an algorithm working in time $O(D+m)$ for arbitrary networks, which is optimal. For the task of gossiping we give an algorithm working in time $O(N(M+D\log L))$ for arbitrary networks. At the time of writing this paper we were unaware of the paper: A. Czumaj, P. Davis, Communicating with Beeps, arxiv:1505.06107 [cs.DC] which contains the same results for broadcasting and a stronger upper bound for gossiping in a slightly different model.
This article deals with some stochastic population protocols, motivated by theoretical aspects of distributed computing. We modelize the problem by a large urn of black and white balls from which at every time unit a fixed number of balls are drawn and their colors are changed according to the number of black balls among them. When the time and the number of balls both tend to infinity the proportion of black balls converges to an algebraic number. We prove that, surprisingly enough, not every algebraic number can be ''computed'' this way.
We develop a version of the pi-calculus, picost, where channels are
interpreted as resources which have costs associated with them. Code runs under
the financial responsibility of owners; they must pay to use resources, but may
profit by providing them. We provide a proof methodology for processes
described in picost based on bisimulations. The underlying behavioural theory
is justified via a contextual characterisation. We also demonstrate its
usefulness via examples.
We start with a set of $n$ players. With some probability $P(n,k)$, we kill $n-k$ players; the other ones stay alive, and we repeat with them. What is the distribution of the number $X_n$ of \emph{phases} (or rounds) before getting only one player? We present a probabilistic analysis of this algorithm under some conditions on the probability distributions $P(n,k)$, including stochastic monotonicity and the assumption that roughly a fixed proportion $\al$ of the players survive in each round. We prove a kind of convergence in distribution for $X_n - \log_{1/\!\alpha}(n)$; as in many other similar problems there are oscillations and no true limit distribution, but suitable subsequences converge, and there is an absolutely continuous random variable $Z$ such that $d\l(X_n, \lceil Z + \log_{1/\!\alpha} (n)\rceil\r) \to 0$, where $d$ is either the total variation distance or the Wasserstein distance. Applications of the general result include the leader election algorithm where players are eliminated by independent coin tosses and a variation of the leader election algorithm proposed by W.R. Franklin. We study the latter algorithm further, including numerical results.
A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has a