Enumeration and Random Generation of Concurrent Computations
Abstrak
In this paper, we study the shuffle operator on concurrent processes (represented as trees) using analytic combinatorics tools. As a first result, we show that the mean width of shuffle trees is exponentially smaller than the worst case upper-bound. We also study the expected size (in total number of nodes) of shuffle trees. We notice, rather unexpectedly, that only a small ratio of all nodes do not belong to the last two levels. We also provide a precise characterization of what ``exponential growth'' means in the case of the shuffle on trees. Two practical outcomes of our quantitative study are presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random generation of concurrent runs.
Topik & Kata Kunci
Penulis (3)
Olivier Bodini
Antoine Genitrini
Frédéric Peschanski
Akses Cepat
- Tahun Terbit
- 2012
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.2986
- Akses
- Open Access ✓