In this paper, we analyze a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This protocol relies on successive pull operations involving$k$different nodes, with$k=2$or$k=3$, and called$k$-pull operations. Specifically during a k-pull operation, an uninformed node$a$contacts$k-1$other nodes at random in the network, and if at least one of them knows the rumor, then node$a$learns it. We perform a detailed study in continuous-time of$\Theta_{k, n}$, the total time needed for all the$n$nodes to learn the rumor. We obtain, for$k\in\{2,3\}$, the mean value, the variance and the distribution of$\Theta_{k, n}$together with their asymptotic behavior when the number of nodes$n$tends to infinity.

This paper proposes and analyses the performance and the vulnerability to attacks of three algorithms for collecting longitudinal data in a large scale system. A monitoring device is in charge of continuously collecting measurements from end-devices. The communication graph is connected but not necessar-ily complete. For scalability reasons, at each collect, a single end-device is randomly selected among all the end -devices to send the content of its local buffer of data to the monitoring device. Once sent, the end-device resets its buffer, and resumes its measurement process. Two of the three algorithms are randomized algorithms while the third one is deterministic. We study the transient and stationary maximum load distribution at end-devices when collects are made using the first and third algorithm, and by providing bounds via a coupling argument when the second algorithm is used. While the third algorithm provides the best performance, it is highly vulnerable to attacks.

We propose a consensus algorithm whose objective is to decide on the same union of proposed values, such that with high probability all the values proposed by the honest nodes belong to the decision. Our algorithm has been designed to cope with an asynchronous and permissionless system. By relying on a proof-of-eligibility, our algorithm is tolerant to an adversary capable of instantaneously corrupting entities. A straightforward application of our algorithm is the design of permissionless distributed ledgers.

The context of this work is the well-studied dissemination of information in large-scale distributed networks through pairwise interactions. This problem, originally called rumor mongering, and then rumor spreading, has mainly been investigated in the synchronous model. This model relies on the assumption that all the nodes of the network act in synchrony; that is, at each round of the protocol, each node is allowed to contact a random neighbor. In this paper, we drop this assumption under the argument that it is not realistic in large-scale systems. We, thus, consider the asynchronous variant, with which, at random times, nodes successively interact by pairs, exchanging their information on the rumor. In a previous paper, we performed a study of the total number of interactions needed for all the nodes of the network to discover the rumor. Although most of the existing results involve huge constants that do not allow us to compare different protocols, we provided a thorough analysis of the distribution of this total number of interactions together with its asymptotic behavior. In this paper, we extend this discrete-time analysis by solving a conjecture proposed previously, and we consider the continuous-time case, in which a Poisson process is associated to each node to determine the instants at which interactions occur. The rumor-spreading time is, thus, more realistic because it is the real time needed for all the nodes of the network to discover the rumor. Once again, as most of the existing results involve huge constants, we provide tight bound and equivalent of the complementary distribution of the rumor-spreading time. We also give the exact asymptotic behavior of the complementary distribution of the rumor-spreading time around its expected value when the number of nodes tends to infinity.

A recent technical breakthrough in the domain of machine learning is the discovery and the multiple applications of Generative Adversarial Networks (GANs). Those generative models are computationally demanding, as a GAN is composed of two deep neural networks, and because it trains on large datasets. A GAN is generally trained on a single server. In this paper, we address the problem of distributing GANs so that they are able to train over datasets that are spread on multiple workers. MD-GAN is exposed as the first solution for this problem: we propose a novel learning procedure for GANs so that they fit this distributed setup. We then compare the performance of MD-GAN to an adapted version of federated learning to GANs, using the MNIST, CIFAR10 and CelebA datasets. MD-GAN exhibits a reduction by a factor of two of the learning complexity on each worker node, while providing better or identical performances with the adaptation of federated learning. We finally discuss the practical implications of distributing GANs.

Mobile video traffic accounted for more than half of all mobile data traffic over the past two years. Due to the limited bandwidth, users demand for high-quality video streaming becomes a challenge, which could be addressed by exploiting the emerging diversity of access network and adaptive video streaming. In this paper, a network selection algorithm is proposed for Dynamic Adaptive Streaming over HTTP (DASH), the famous international standard on video streaming, to enhance the received video quality to a "multi-homed user" equipped with multiple interfaces. A Multi-Armed Bandit (MAB) heuristic is proposed for a dynamic selection of the best interface at each step. While the Adaptive Bitrate Rules (ABR) used in DASH allow the video player client to dynamically pick the bit rate level according to the perceived network conditions, at each switching step a quality degradation may occur due to the difference in network conditions of the available interfaces. This paper aims to close this gap by (i) designing a MAB algorithm over DASH for a multi-homed user, (ii) evaluating the proposed mechanism through a test-bed implementation, (iii) extending the classic MAB model and (iv) discussing some open issues.

We propose a new way to organise both transactions and blocks in a distributed ledger to address the performance issues of permissionless ledgers. In contrast to most of the existing solutions in which the ledger is a chain of blocks extracted from a tree or a graph of chains, we present a distributed ledger whose structure is a balanced directed acyclic graph of blocks. We call this specific graph a SYC-DAG. We show that a SYC-DAG allows us to keep all the remarkable properties of the Bitcoin blockchain in terms of security, immutability, and transparency, while enjoying higher throughput and self-adaptivity to transactions demand. To the best of our knowledge, such a design has never been proposed so far.

This paper focuses on pairwise interaction-based protocols, and proposes an universal mechanism that allows each agent to locally detect that the system has converged to the sought configuration with high probability. To illustrate our mechanism, we use it to detect the instant at which the proportion problem is solved. Specifically, let nA(resp. nB) be the number of agents that initially started in state nA(resp. B) and γA= nA/n, where n is the total number of agents. Our protocol guarantees, with a given precision ε > 0 and any high probability 1 - 6, that after O (n ln(n/δ)) interactions, any queried agent that has set the detection flag will output the correct value of the proportion γAof agents which started in state A, by maintaining no more than O (ln(n)/ε) integers. We are not aware of any such results. Simulation results illustrate our theoretical analysis.

A large portion of data mining and analytic services use modern machine learning techniques, such as deep learning. The state-of-the-art results by deep learning come at the price of an intensive use of computing resources. The leading frameworks (e.g., TensorFlow) are executed on GPUs or on high-end servers in datacenters. On the other end, there is a proliferation of personal devices with possibly free CPU cycles; this can enable services to run in users' homes, embedding machine learning operations. In this paper, we ask the following question: Is distributed deep learning computation on WAN connected devices feasible, in spite of the traffic caused by learning tasks? We show that such a setup rises some important challenges, most notably the ingress traffic that the servers hosting the up-to-date model have to sustain. In order to reduce this stress, we propose AdaComp, a novel algorithm for compressing worker updates to the model on the server. Applicable to stochastic gradient descent based approaches, it combines efficient gradient selection and learning rate modulation. We then experiment and measure the impact of compression, device heterogeneity and reliability on the accuracy of learned models, with an emulator platform that embeds TensorFlow into Linux containers. We report a reduction of the total amount of data sent by workers to the server by two order of magnitude (e.g., 191-fold reduction for a convolutional network on the MNIST dataset), when compared to a standard asynchronous stochastic gradient descent, while preserving model accuracy.

We consider a large system populated by n anonymous nodes that communicate through asynchronous and pair-wise interactions. The aim of these interactions is for each node to converge toward a global property of the system, that depends on the initial state of each node. In this paper we focus on both the counting and proportion problems. We show that for any δ ϵ (0, 1), the number of interactions needed per node to converge is O(ln(n/δ)) with probability at least 1-δ. We also prove that each node can determine, with any high probability, the proportion of nodes that initially started in a given state without knowing the number of nodes in the system. This work provides a precise analysis of the convergence bounds, and shows that using the 4-norm is very effective to derive useful bounds.

Decentralized cryptocurrency systems offer a medium of exchange secured by cryptography, without the need of a centralized banking authority. Among others, Bitcoin is considered as the most mature one. Its popularity lies on the introduction of the concept of the blockchain, a public distributed ledger shared by all participants of the system. Double spending attacks and blockchain forks are two main issues in blockchain-based protocols. The first one refers to the ability of an adversary to use the very same bitcoin more than once, while blockchain forks cause transient inconsistencies in the blockchain. We show through probabilistic analysis that the reliability of recent solutions that exclusively rely on a particular type of Bitcoin actors, called miners, to guarantee the consistency of Bitcoin operations, drastically decreases with the size of the blockchain.

The computational model of population protocols is a formalism that allows the analysis of properties emerging from simple and pairwise interactions among a very large number of anonymous finite-state agents. Significant work has been done so far to determine which problems are solvable in this model and at which cost in terms of states used by the agents and time needed to converge. The problem tackled in this paper is the population proportion problem: each agent starts independently from each other in one of two states, say A or B, and the objective is for each agent to determine the proportion of agents that initially started in state A, assuming that each agent only uses a finite set of states, and does not know the number n of agents. We propose a solution which guarantees that in presence of a uniform probabilistic scheduler every agent outputs the population proportion with any precision ε ∈ (0, 1) with any high probability after having interacted O(log n) times. The number of states maintained by every agent is optimal and is equal to 2⌈3/(4ε)⌉+1. Finally, we show that our solution is optimal in time and space to solve the counting problem, a generalization of the proportion problem. Finally, simulation results illustrate our theoretical analysis.

The context of this work is the well studied dissemination of information in large scale distributed networks through pairwise interactions. This problem, originally called rumor mongering, and then rumor spreading has mainly been investigated in the synchronous model. This model relies on the assumption that all the nodes of the network act in synchrony, that is, at each round of the protocol, each node is allowed to contact a random neighbor. In this paper, we drop this assumption under the argument that it is not realistic in large scale systems. We thus consider the asynchronous variant, where at time unit, a single node interacts with a randomly chosen neighbor. We perform a thorough study of Tn the total number of interactions needed for all the n nodes of the network to discover the rumor. While most of the existing results involve huge constants that do not allow for comparing different protocols, we prove that in a complete graph of size n ≥ 2, the probability that Tn> k for all k ≥ 1 is less than (1+(2k(n-2)2)/(n))(1-2/n)(k-1). We also study the behavior of the complementary distribution of Tnat point cE(Tn) when n tends to infinity for c ≠ 1. We end our analysis by conjecturing that when n tends to infinity, Tn> E(Tn) with probability close to 0.4484.

To cope with the tremendous growth in mobile data traffic on one hand, and the modest average revenue per user on the other hand, mobile operators have been exploring network virtualization and cloud computing technologies to build cost-efficient and elastic mobile networks and to have them offered as a cloud service. In such cloud-based mobile networks, ensuring service resilience is an important challenge to tackle. Indeed, high availability and service reliability are important requirements of carrier grade, but not necessarily intrinsic features of cloud computing. Building a system that requires the five nines reliability on a platform that may not always grant it is, therefore, a hurdle. Effectively, in carrier cloud, service resilience can be heavily impacted by a failure of any network function (NF) running on a virtual machine (VM). In this paper, we introduce a framework, along with efficient and proactive restoration mechanisms, to ensure service resilience in carrier cloud. As restoration of a NF failure impacts a potential number of users, adequate network overload control mechanisms are also proposed. A mathematical model is developed to evaluate the performance of the proposed mechanisms. The obtained results are encouraging and demonstrate that the proposed mechanisms efficiently achieve their design goals.

We consider in this paper an important Quality of Experience (QoE) indicator in mobile networks that is reneging of users due to impatience. We specifically consider a cell under heavy load conditions and compute the reneging probability by using a fluid limit analysis. By solving the fixed point equation, we obtain a new QoE perturbation metric quantifying the impact of reneging on the performance of the system. This metric is then used to devise a new pricing scheme accounting of reneging. We specifically propose several flavors of this pricing around the idea of having a flat rate for accessing the network and an elastic price related to the level of QoE perturbation induced by communications.

This paper presents a solution to the well-known Test-and-Set operation in asynchronous systems prone to process crashes. Test-and-Set is a synchronization operation that, when invoked by a set of processes, returns "yes" to a unique process and returns "no" to all the others. Recently many advances in implementing Test and Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test-and-Set object for message passing distributed systems. This implementation can be invoked by any number p of processes. It has an expected step complexity in O(p) and an expected message complexity in O(np), where n is the total number of processes in the system. The proposed Test and Set object is built atop a new basic building block that allows to select a winning group among two groups of processes.

The population protocol model provides theoretical foundations for analyzing the properties emerging from simple and pair wise interactions among a very large number n of anonymous agents. The problem tackled in this paper is the following one: is there an efficient population protocol that exactly counts the difference k between the number of agents that initially and independently set their state to "A" and the one that initially set it to "B", assuming that each agent only uses a finite set of states? We propose a solution which guarantees with any high probability that after O(log n) interactions any agent outputs the exact value of k. Simulation results illustrate our theoretical analysis.

We consider the problem of identifying global iceberg attacks in massive and physically distributed streams. A global iceberg is a distributed denial of service attack, where some elements globally recur many times across the distributed streams, but locally, they do not appear as a deny of service. A natural solution to defend against global iceberg attacks is to rely on multiple routers that locally scan their network traffic, and regularly provide monitoring information to a server in charge of collecting and aggregating all the monitored information. Any relevant solution to this problem must minimise the communication between the routers and the coordinator, and the space required by each node to analyse its stream. We propose a distributed algorithm that tracks global icebergs on the fly with guaranteed error bounds, limited memory and processing requirements. We present a thorough analysis of our algorithm performance. In particular we derive a tight upper bound on the number of bits communicated between the multiple routers and the coordinator in presence of an oblivious adversary. Finally, we present the main results of the experiments we have run on a cluster of single-board computers. Those experiments confirm the efficiency and accuracy of our algorithm to track global icebergs hidden in very large input data streams exhibiting different shapes.

The context of this work is the online characterization of errors in large scale systems. In particular, we address the following question: Given two successive configurations of the system, can we distinguish massive errors from isolated ones, the former ones impacting a large number of nodes while the second ones affect solely a small number of them, or even a single one? The rationale of this question is twofold. First, from a theoretical point of view, we characterize errors with respect to their neighbourhood, and we show that there are error scenarios for which isolated and massive errors are indistinguishable from an omniscient observer point of view. We then relax the definition of this problem by introducing unresolved configurations, and exhibit necessary and sufficient conditions that allow any node to determine the type of errors it has been impacted by. These conditions only depend on the close neighbourhood of each node and thus are locally computable. We present algorithms that implement these conditions, and show through extensive simulations, their performances. Now from a practical point of view, distinguishing isolated errors from massive ones is of utmost importance for networks providers. For instance, for Internet service providers that operate millions of home gateways, it would be very interesting to have procedures that allow gateways to self distinguish whether their dysfunction is caused by network-level errors or by their own hardware or software, and to notify the service provider only in the latter case.

We consider the problem of achieving uniform node sampling in large scale systems in presence of a strong adversary. We first propose an omniscient strategy that processes on the fly an unbounded and arbitrarily biased input stream made of node identifiers exchanged within the system, and outputs a stream that preserves Uniformity and Freshness properties. We show through Markov chains analysis that both properties hold despite any arbitrary bias introduced by the adversary. We then propose a knowledge-free strategy and show through extensive simulations that this strategy accurately approximates the omniscient one. We also evaluate its resilience against a strong adversary by studying two representative attacks (flooding and targeted attacks). We quantify the minimum number of identifiers that the adversary must insert in the input stream to prevent uniformity. To our knowledge, such an analysis has never been proposed before.

In this paper we consider the problem of targeted attacks in large scale peer-to-peer overlays. These attacks aimed at exhausting key resources of targeted hosts to diminish their capacity to provide or receive services. To defend the system against such attacks, we rely on clustering and implement induced churn to preserve randomness of nodes identifiers so that adversarial predictions are impossible. We propose robust join, leave, merge and split operations to discourage brute force denial of services and pollution attacks. We show that combining a small amount of randomization in the operations, and adequately tuning the sojourn time of peers in the same region of the overlay allows first to decrease the effect of targeted attacks at cluster level, and second to prevent pollution propagation in the whole overlay.

In this paper we present an analytic study of the impact of churn in cluster-based overlay networks. Cluster-based overlays keep the best of unstructured and structured overlays in terms of scalability, fault-tolerance and stability. Most of join and leave events have no impact on the overall overlay topology making these overlays highly robust to high churn. The only situations that effectively give rise to topology modifications are when clusters need to split because they exceed some maximal size or need to merge because they fall under some minimal size. Although these operations are scalable, they are intricate in the sense that they need synchronization among nodes involved in these operations. In this paper we accurately predict the frequency at which the topology of the overlay changes according to the number of join/leave operations. Our analysis improves upon existing studies by showing that these relevant topological changes are very infrequent, namely θ(N) join/leave events are required before any of these topological operations occur, where N is the number of peers currently in the system. Such a result clearly demonstrates the appropriateness of these overlays to high churn.

The paper "performability analysis: a new algorithmrdquo describes an algorithm for computing the complementary distribution of the accumulated reward over an interval of time in a homogeneous Markov process. In this comment, we show that in two particular cases, one of which is quite frequent, small modifications of the algorithm may reduce significantly its storage complexity.

Awerbuch and Scheideler have shown that peer-to-peer overlays networks can survive Byzantine attacks only if malicious nodes are not able to predict what will be the topology of the network for a given sequence of join and leave operations. In this paper we investigate adversarial strategies by following specific protocols. Our analysis demonstrates first that an adversary can very quickly subvert DHT-based overlays by simply never triggering leave operations. We then show that when all nodes (honest and malicious ones) are imposed on a limited lifetime, the system eventually reaches a stationary regime where the ratio of polluted clusters is bounded, independently from the initial amount of corruption in the system.

Efficient mobility management is one of the major challenges for next-generation mobile systems. Indeed, a mobile node (MN) within an access network may cause excessive signaling traffic and service disruption due to frequent handoffs. The two latter effects need to be minimized to support quality of service (QoS) requirements of emerging multimedia applications. In this paper, we propose a new adaptive micromobility management scheme designed to track efficiently the mobility of nodes so as to minimize both handoff latency and total signaling cost while ensuring the MN's QoS requirements. We introduce the concept of residing area. Accordingly, the micromobility domain is divided into virtual residing areas where the MN limits its signaling exchanges within this local region instead of communicating with the relatively far away root of the domain at each handoff occurrence. A key distinguishing feature of our solution is its adaptive nature since the virtual residing areas are constructed according to the current network state and the QoS constraints. To evaluate the efficiency of our proposal, we compare our scheme with existing solutions using both analytical and simulation approaches for the 2-D random walk model as well as real mobility patterns. Numerical and simulation results show that our proposed scheme can significantly reduce registration updates and link usage costs and provide low handoff latency and packet loss rate under various scenarios.

One the of major challenges of optical network operators is ensuring the stringent levels of availability required by their highest class clients. To achieve this, we introduce relative priorities among the different primary connections contending for access to the shared-protection paths. In this paper, we provide an analytical model for the proposed priority-enabled scheme. As a key distinguishing feature from existing literature, we derive explicit analytic expressions for average the availability and service disruption rate for the different priority classes.

Point availability and expected interval availability are dependability measures respectively defined by the probability that a system is in operation at a given instant and by the mean percentage of time during which a system is in operation over a finite observation period. We consider a repairable computer system and we assume, as usual, that the system is modeled by a finite Markov process. We propose in this paper a new algorithm to compute these two availability measures. This algorithm is based on the classical uniformization technique in which a test to detect the stationary behavior of the system is used to stop the computation if the stationarity is reached. In that case, the algorithm gives not only the transient availability measures, but also the steady state availability, with significant computational savings, especially when the time at which measures are needed is large. In the case where the stationarity is not reached, the algorithm provides the transient availability measures and bounds for the steady state availability. It is also shown how the new algorithm can be extended to the computation of performability measures.

We propose, in this paper, a new algorithm to compute the performability distribution. Its computational complexity is polynomial and it deals only with nonnegative numbers bounded by one. This important property allows us to determine truncation steps and so to improve the execution time of the algorithm.

Interval availability is a dependability measure defined by the fraction of time during which a system is operational over a finite observation period. The computation of its distribution allows the user to ensure that the probability that its system will achieve a given availability level is high enough. The system is assumed to be modeled as a Markov process with countable state space. We propose a new algorithm to compute the interval availability distribution. One of its main advantages is that, in some cases, it applies even to infinite state spaces. This is useful, for instance, in case of models taking into account contention with unbounded buffers. This important feature is illustrated on models of multiprocessor systems, subject to breakdowns and repair. When the model is finite, we show through a numerical example that the new technique can perform very well.>

M.D. Beaudry (1978) proposed a simple method of computing the distribution of performability in a Markov reward process. Two extensions of Beaudry's approach are presented. The authors generalize the method to a semi-Markov reward process by removing the restriction requiring the association of zero reward to absorbing states only. The algorithm proceeds by replacing zero reward nonabsorbing states by a probabilistic switch; it is therefore related to the elimination of vanishing states from the reachability graph of a generalized stochastic Petri net and to the elimination of fast transient states in a decomposition approach to stiff Markov chains. The use of the approach is illustrated with three applications.>