Abstract
The study of concurrent processes with conflict points is connected with the geometry of increasing subsequences of permutations - a permutation encodes the transactions of two processes that conflict (i.e., must be executed serially), and a given increasing subsequence encodes one particular serialization of the executions of two processes. This motivates the study of random increasing subsequences of random permutations. Here, we give a large deviation principle which implies that such a subsequence never deviates too far from the identity permutation: a random serialization of two concurrent processes will not favor either process too much at any given time. We then give an efficient exact algorithm for uniform random sampling of an increasing subsequence from a given permutation.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 39-41 |
| Number of pages | 3 |
| Journal | Performance Evaluation Review |
| Volume | 45 |
| Issue number | 2 |
| DOIs | |
| State | Published - Sep 1 2017 |
| Event | Workshop on MAthematical Performance Modeling and Analysis, MAMA 2017, 2017 Greenmetrics Workshop and Workshop on Critical Infrastructure Network Security, CINS 2017 - Urbana-Champaign, United States Duration: Jun 1 2017 → … |
Fingerprint
Keywords
- Increasing subsequences
- Large deviations
- Permutations
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications
Cite this
Large deviations for increasing subsequences of permutations and a concurrency application. / Baryshnikov, Yuliy; Magner, Abram.
In: Performance Evaluation Review, Vol. 45, No. 2, 01.09.2017, p. 39-41.Research output: Contribution to journal › Conference article
}
TY - JOUR
T1 - Large deviations for increasing subsequences of permutations and a concurrency application
AU - Baryshnikov, Yuliy
AU - Magner, Abram
PY - 2017/9/1
Y1 - 2017/9/1
N2 - The study of concurrent processes with conflict points is connected with the geometry of increasing subsequences of permutations - a permutation encodes the transactions of two processes that conflict (i.e., must be executed serially), and a given increasing subsequence encodes one particular serialization of the executions of two processes. This motivates the study of random increasing subsequences of random permutations. Here, we give a large deviation principle which implies that such a subsequence never deviates too far from the identity permutation: a random serialization of two concurrent processes will not favor either process too much at any given time. We then give an efficient exact algorithm for uniform random sampling of an increasing subsequence from a given permutation.
AB - The study of concurrent processes with conflict points is connected with the geometry of increasing subsequences of permutations - a permutation encodes the transactions of two processes that conflict (i.e., must be executed serially), and a given increasing subsequence encodes one particular serialization of the executions of two processes. This motivates the study of random increasing subsequences of random permutations. Here, we give a large deviation principle which implies that such a subsequence never deviates too far from the identity permutation: a random serialization of two concurrent processes will not favor either process too much at any given time. We then give an efficient exact algorithm for uniform random sampling of an increasing subsequence from a given permutation.
KW - Increasing subsequences
KW - Large deviations
KW - Permutations
UR - http://www.scopus.com/inward/record.url?scp=85041394574&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041394574&partnerID=8YFLogxK
U2 - 10.1145/3152042.3152056
DO - 10.1145/3152042.3152056
M3 - Conference article
AN - SCOPUS:85041394574
VL - 45
SP - 39
EP - 41
JO - Performance Evaluation Review
JF - Performance Evaluation Review
SN - 0163-5999
IS - 2
ER -