Markov chains competing for transitions: application to large-scale distributed systems

DOI10.1007/S11009-011-9239-6MaRDI QIDQ352904zbMATH OpenOpenAlexFDO

Authors Emmanuelle Anceaume, Romaric Ludinard, Bruno Sericola, Francois Castella

Publication date 5 July 2013

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11009-011-9239-6

zbMATH Keywords

absorbing Markov chainscomposition of Markov chainsfirst time until absorption

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical analysis or methods applied to Markov chains (65C40)

Review text

This paper considers the parallel composition of many identical, but not necessarily independent, absorbing discrete-time Markov chains. A randomised scheduling policy is used to determine the Markov chain that performs the next transition. The central focus of the paper is to determine the first time at which one of the Markov chains reaches its absorbing state. The authors obtain the probability distribution as well as the expectation of this measure, and provide polynomial-time algorithms to obtain these quantities. Asymptotic results are obtained when the number of Markov chains goes to infinity. The results are applied to cluster merging and splitting in large distributed networks.

Recommendations

• Analysis of a large number of Markov chains competing for transitions
• Waiting time distributions of competing patterns in higher-order Markovian sequences
• Rare event analysis of the state frequencies of a large number of Markov chains
• scientific article; zbMATH DE number 2006656
• A theory of distributed Markov chains

Cites work

• Algorithms – ESA 2005
• Automata, Languages and Programming
• scientific article; zbMATH DE number 3679828 (Why is no real title available?)
• scientific article; zbMATH DE number 3736679 (Why is no real title available?)
• scientific article; zbMATH DE number 3736680 (Why is no real title available?)
• scientific article; zbMATH DE number 2080510 (Why is no real title available?)
• scientific article; zbMATH DE number 2080852 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)

Cited in

(6)

• Markov chains for collaboration
• On Clusters in Markov Chains
• Markov Teams ? An analytical approach to process migration in distributed computing systems
• scientific article; zbMATH DE number 2006656 (Why is no real title available?)
• Analysis of a large number of Markov chains competing for transitions
• Computing absorbing times via fluid approximations

Describes a project that uses

Uses Software

• Chord

This page was built for publication: Markov chains competing for transitions: application to large-scale distributed systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q352904)