Search

Part 6: Large-Scale Decentralised Systems; International audience; Gossip protocols form the basis of many smart collective adaptive systems. They are a class of fully decentralised, simple but robust protocols for the distribution of information throughout large scale networks with hundreds or thousands of nodes. Mean field analysis methods have made it possible to approximate and analyse performance aspects of such large scale protocols in an efficient way that is independent of the number of nodes in the network. Taking the gossip shuffle protocol as a benchmark, we evaluate a recently developed refined mean field approach. We illustrate the gain in accuracy this can provide for the analysis of medium size models analysing two key performance measures: replication and coverage. We also show that refined mean field analysis requires special attention to correctly capture the coordination aspects of the gossip shuffle protocol.

International audience; A stochastic multi-agent opinion dynamics model is proposed and analyzed, in which, the multi-leveled opinion of each agent is influenced by a random neighbor's binary action, determined by its opinion level. This model is shown to asymptotically produce consensus with a finite number of connected agents. On the other hand, when the number of agents is large, the time to achieve consensus can become exponentially high, potentially resulting in other equilibrium points based on the structure of the connectivity graph. Numerical simulations validate the proposed analysis, and demonstrate these other equilibrium points, that exist when a large number of agents are present.

Across defense, homeland security, and law enforcement communities, leaders face the tension between making quick but also well informed decisions regarding time-dependent entities of interest. For example, consider a law enforcement organization (searcher) with a sizable list of potential terrorists (targets) but far fewer observational assets (sensors). The searcher's goal being to follow the target, but resource constraints make continuous coverage impossible, resulting in intermittent observational attempts.We model target behaviour as a discrete time Markov chain with the state space being the target's set of possible locations, activities, or attributes. In this setting, we define following the target as the searcher, at any given time step, correctly identifying and then allocating the sensor to the state which has the highest probability of containing the target. In other words, in each time period the searcher's objective is to decide where to send the sensor, attempting to observe the target in that time period, resulting in a hit or miss from which the searcher learns the target's true transition behaviour. We develop a Multi-Armed Bandit approach for efficiently following the target, where each state takes the place of an arm. Our search policy is five to ten times better than existing approaches. http://archive.org/details/amultiarmedbandi1094555572 Outstanding Thesis Captain, United States Marine Corps Approved for public release; distribution is unlimited.

Binary search algorithm (BS) is a kind of important anti-collision algorithm in the Radio Frequency Identification (RFID), is also one of the key technologies which determine whether the information in the tag is identified by the reader-writer fast and reliably. The performance of BS directly affects the quality of service in Internet of Things. This paper adopts an automated formal technology: probabilistic model checking to analyze the performance of BS algorithm formally. Firstly, according to the working principle of BS algorithm, its dynamic behavior is abstracted into a Discrete Time Markov Chains which can describe deterministic, discrete time and the probability selection. And then on the model we calculate the probability of the data sent successfully and the expected time of tags completing the data transmission. Compared to the another typical anti-collision protocol S-ALOHA in RFID, experimental results show that with an increase in the number of tags the BS algorithm has a less space and time consumption, the average number of conflicts increases slower than the S-ALOHA protocol standard, BS algorithm needs fewer expected time to complete the data transmission, and the average speed of the data transmission in BS is as 1.6 times as the S-ALOHA protocol.

Collective Adaptive Systems (CAS) consist of a large number of interacting objects. The design of such systems requires scalable analysis tools and methods, which have necessarily to rely on some form of approximation of the system's actual behaviour. Promising techniques are those based on mean-field approximation. The FlyFast model-checker uses an on-the- y algorithm for bounded PCTL model-checking of selected individual(s) in the context of very large populations whose global behaviour is approximated using deterministic limit mean-field techniques. Recently, a front-end for FlyFast has been proposed which provides a modelling language, PiFF in the sequel, for the Predicate-based Interaction for FlyFast. In this paper we present details of PiFF design and an approach to state-space reduction based on probabilistic bisimulation for inhomogeneous DTMCs.

This paper presents a new decomposition method for the approximate performance evaluation of buffered multi-stage production systems where machines are modeled as generally complex discrete time Markov chains with reward. The method is based on the exact solution of smaller two-machine sub-systems, also referred as building blocks, with machines that also feature such general characteristics. A decomposition approach is developed that propagates all the possible interruptions of flow due to starvation and blocking conditions throughout the pseudo-machines of each building block. In order to deal with such general settings, new decomposition equations are developed. A new algorithm is proposed for solving these decomposition equations. The proposed method proves to be very fast and accurate over a wide range of test cases, partly reported in this paper. To prove the generality of the framework, reported cases are focused on systems with generally distributed up and down times and systems with degrading machines. This method paves the way to the analysis of a wider class of previously un-investigated systems.

Opportunistic Routing (OR) has been investigated in recent years as a way to increase the performance of multihop wireless networks by exploiting its broadcast nature. In contrast to traditional routing, where traffic is sent along pre-determined paths, in OR an ordered set of candidates is selected for each next-hop. Upon each transmission, the candidates coordinate such that the most priority one receiving the packet actually forwards it. Most of the research in OR has been addressed to investigate candidate selection algorithms. In this paper we propose a discrete time Markov chain to assess the improvement that may be achieved using opportunistic routing. We use our model to compare a selected group of candidate selection algorithms that have been proposed in the literature. Our main conclusion is that optimality is obtained at a high computational cost, with a performance gain very similar to that of much simpler but non-optimal algorithms. Therefore, we conclude that fast and simple OR candidate selection algorithms may be preferable in dynamic networks, where the candidates sets are likely to be updated frequently. © 2011 Elsevier B.V. All rights reserved., This work was supported by the Spanish government through projects TIN2010-21378-C02-01 and TIN2010-21378-C02-02, by the Generalitat de Catalunya through project 2009-SGR-1167, and by the European Commission through the NoE EuroNF.

Typical Collective Adaptive Systems (CAS) consist of a large number of interacting objects that coordinate their activities in a decentralised and often implicit way. The design of such systems is challenging. It requires scalable analysis tools and techniques to check properties of proposed system designs before they are put into operation. A promising technique is Fast Mean- Field Approximated Model-checking. In particular, the FlyFast model-checker uses an on-the-fly algorithm for bounded PCTL model-checking of selected individuals in the context of very large populations whose global behaviour is approximated using deterministic limit techniques. Recently, specific modelling languages have been proposed for CAS. A key feature of such languages is the attribute-based interaction paradigm. In this paper we present a simple non value-passing version of an attribute-based coordination language as a front-end for FlyFast. Its formal probabilistic semantics is provided and a translation to the original FlyFast language is presented and proved correct. Application examples are also provided.

International audience; Typical Collective Adaptive Systems (CAS) consist of a large number of interacting objects that coordinate their activities in a decentralised and often implicit way. The design of such systems is challenging, as it requires scalable analysis tools and methods to check properties of proposed system designs before they are put into operation. A promising technique is Fast Mean-Field Approximated Model-checking. The FlyFast model-checker uses an on-the-fly algorithm for bounded PCTL model-checking of selected individuals in the context of very large populations whose global behaviour is approximated using deterministic limit techniques. Recently, specific modelling languages have been proposed for CAS. A key feature of such languages is the attribute-based interaction paradigm. In this paper we present an attribute-based coordination language as a front-end for FlyFast. Its formal probabilistic semantics is provided and a translation to the original FlyFast language is given and proved correct. Application examples are also provided.

We show that, under suitable convergence and scaling conditions, fluid model checking bounded CSL formulas on selected individuals in a continuous large population model can be approximated by checking equivalent bounded PCTL formulas on corresponding objects in a discrete time, time synchronous Markov population model, using an on-the-fly mean field approach. The proposed technique is applied to a benchmark epidemic model and a client-server case study showing promising results also for the challenging case of nested formulas with time dependent truth values. The on-the-fly results are compared to those obtained via global fluid model checking and statistical model-checking.

We consider an example network where we compute the bounds on cell loss rates. The stochastic bounds for these loss rates using simple arguments lead to models easier to solve. We proved, using stochastic orders, that the loss rates of these easier models are really the bounds of our original model. For ill-balanced configurations these models give good estimates of loss rates.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. In this study, we investigate a single-item, periodic-review inventory problem where the production capacity is limited and unmet demand is backordered. We assume that customer demand in each period is a stationary, discrete random variable. Linear holding and backorder cost are charged per unit at the end of a period. In addition to the variable cost charged per unit ordered, a positive fixed ordering cost is incurred with each order given. The optimization criterion is the minimization of the expected cost per period over a planning horizon. We investigate the infinite horizon problem by modeling the problem as a discrete-time Markov chain. We propose a heuristic for the problem based on a particular solution of this stationary model, and conduct a computational study on a set of instances, providing insight on the performance of the heuristic.

A novel, scalable, on-the-fly model-checking procedure is presented to verify bounded PCTL properties of selected individuals in the context of very large systems of independent interacting objects. The proposed procedure combines on-the-fly model checking techniques with deterministic mean-field approximation in discrete time. The asymptotic correctness of the procedure is shown and some results of the application of a prototype implementation of the FlyFast model-checker are presented.

International audience; We investigate how we can bound a discrete time Markov chain (DTMC) by a stochastic matrix with a low rank decomposition. In the first part of the article, we show the links with previous results for matrices with a decomposition of size 1 or 2. Then we show how the complexity of the analysis for steady-state and transient distributions can be simplified when we take into account the decomposition. Finally, we show how we can obtain a monotone stochastic upper bound with a low rank decomposition.

Time reversibility plays an important role in the analysis of continuous and discrete time Markov chains (DTMCs). Specifically, the computation of the stationary distribution of a reversible Markov chain has been proved to be very efficient and does not require the solution of the system of global balance equations. A DTMC is reversible when the processes at forward and reversed time are probabilistically indistinguishable. In this paper we introduce the concept of ρ-reversibility, i.e., a notion of reversibility modulo a renaming of the states, and we contrast it with the previous definition of dynamic reversibility especially with respect to the assumptions on the state renaming function. We discuss the applications of discrete time reversibility in the embedded and uniformized chains of continuous time processes.

Formal analysis techniques are widely used today in order to verify and analyze communication protocols. In this work, we launch a quantitative verification analysis for the low- cost Radio Frequency Identification (RFID) protocol proposed by Song and Mitchell. The analysis exploits a Discrete-Time Markov Chain (DTMC) using the well-known PRISM model checker. We have managed to represent up to 100 RFID tags communicating with a reader and quantify each RFID session according to the protocol's computation and transmission cost requirements. As a consequence, not only does the proposed analysis provide quantitative verification results, but also it constitutes a methodology for RFID designers who want to validate their products under specific cost requirements., Comment: To appear in the 36th IEEE Conference on Local Computer Networks (LCN 2011)

Environmental energy is becoming a feasible alternative for many low-power systems, such as wireless sensor nodes. Designing an environmentally powered device faces several challenges: choosing the exact type of the energy harvester, the energy storage elements and determining the duty cycle of the application. With harvesting, the design process becomes even more difficult because it also has to take into account the unpredictability of the energy source. The contribution of this paper is a methodology that facilitates the analysis of energy harvesting nodes. The existing modeling strategies for battery powered systems are not suitable because they do not capture the uncertainty of the power source. Also, the metrics of interest for battery powered devices are different, as opposed to the harvesting powered ones: in the former case we search to maximize the system lifetime, while in the latter case a more expressive goal is to increase the system availability.

Date of Conference: 10 October, 2006 Conference name: SMCtools '06 Proceeding from the 2006 workshop on Tools for solving structured Markov chains The problem of computing bounds on the conditional steady-state probability vector of a subset of states in finite, ergodic discrete-time Markov chains (DTMCs) is considered. An improved algorithm utilizing the strong stochastic (st-)order is given. On standard benchmarks from the literature and other examples, it is shown that the proposed algorithm performs better than the existing one in the strong stochastic sense. Furthermore, in certain cases the conditional steady-state probability vector of the subset under consideration can be obtained exactly. Copyright 2006 ACM.

Decentralized dynamic (closed-loop) optimal control strategies are sought for a class of finite state Markov decision processes, characterized by the sharing of a common past after k steps of delay. The control is considered over a finite time horizon, and it is shown that a nonclassical dynamic programming procedure can be applied, based on the existence of a sufficient statistic of constant dimension. Finally, the infinite horizon case is briefly discussed, in view of an extention of existing results on the minimization of average expected cost for the centralized and decentralized control of Markov chains.