Large deviations for increasing subsequences of permutations and a concurrency application

Yuliy Baryshnikov, Abram Magner

Research output: Contribution to journalConference article

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 languageEnglish (US)
Pages (from-to)39-41
Number of pages3
JournalPerformance Evaluation Review
Volume45
Issue number2
DOIs
StatePublished - Sep 1 2017
EventWorkshop 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

Sampling
Geometry

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 journalConference article

@article{766670c11f5e492c9d100d6e7180ac15,
title = "Large deviations for increasing subsequences of permutations and a concurrency application",
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.",
keywords = "Increasing subsequences, Large deviations, Permutations",
author = "Yuliy Baryshnikov and Abram Magner",
year = "2017",
month = "9",
day = "1",
doi = "10.1145/3152042.3152056",
language = "English (US)",
volume = "45",
pages = "39--41",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

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 -