Synchronization of Bernoulli sequences on shared letters

DOI10.1016/J.IC.2017.04.002zbMATH Open1371.68183arXiv1506.06537OpenAlexW2271634689MaRDI QIDQ2013553FDOQ2013553

Samy Abbes

Publication date: 8 August 2017

Published in: Information and Computation (Search for Journal in Brave)

Abstract: The topic of this paper is the distributed and incremental generation of long executions of concurrent systems, uniformly or more generally with weights associated to elementary actions. Synchronizing sequences of letters on alphabets sharing letters are known to produce a trace in the concurrency theoretic sense, i.e., a labeled partially ordered set. We study the probabilistic aspects by considering the synchronization of Bernoulli sequences of letters, under the light of Bernoulli and uniform measures recently introduced for trace monoids. We introduce two algorithms that produce random traces, using only local random primitives. We thoroughly study some specific examples, the path model and the ring model, both of arbitrary size. For these models, we show how to generate any Bernoulli distributed random traces, which includes the case of uniform generation.

Full work available at URL: https://arxiv.org/abs/1506.06537

Recommendations

• Uniform generation in trace monoids
• Uniform and Bernoulli measures on the boundary of trace monoids
• scientific article; zbMATH DE number 2086409
• SOME LIMIT DISTRIBUTIONS IN ANALYSIS OF ALGORITHMS FOR PROBLEMS ON TRACE LANGUAGES
• On the synchronization of traces

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Title not available (Why is that?)
• Random Walks on Infinite Graphs and Groups
• Non-negative matrices and Markov chains. 2nd ed
• Combinatorics on traces
• Title not available (Why is that?)
• Combinatorial problems of commutation and rearrangements
• Clique polynomials have a unique root of smallest modulus
• Title not available (Why is that?)
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Lectures on Petri nets. 1: Basic models. Advances in Petri nets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the average parallelism in trace monoids.
• Uniform and Bernoulli measures on the boundary of trace monoids
• Uniform Generation in Trace Monoids
• Asynchronous Games over Tree Architectures
• A linear algorithm for the random sampling from regular languages

Cited In (2)

• Title not available (Why is that?)
• Mixed nondeterministic-probabilistic automata: blending graphical probabilistic models with nondeterminism

This page was built for publication: Synchronization of Bernoulli sequences on shared letters

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