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 conflicts aecting concurrent execution has been long related to various geometric objects. In the special case of two processes and non-overlapping conflicts (definitions below) an instance of a problem is encoded by a permutation describing the conflict sets for the interacting processes. Further, it turns out that the set of increasing subsequences of the permutation describes the homotopy classes of the execution plans for the concurrent processes, an abstraction encoding 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 delay either process's access to shared resources 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. Finally, we indicate how our results generalize to larger numbers of processes, wherein conflict sets may take on more interesting geometries.

Original languageEnglish (US)
Pages (from-to)84-89
Number of pages6
JournalPerformance Evaluation Review
Volume45
Issue number3
DOIs
StatePublished - Mar 20 2018
Event35th IFIP International Symposium on Computer Performance, Modeling, Measurements and Evaluation, IFIP WG 7.3 Performance 2017 - New York, United States
Duration: Nov 13 2017Nov 17 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. 3, 20.03.2018, p. 84-89.

Research output: Contribution to journalConference article

@article{1d36b97384d746fd8b2fd2ae8f2585c0,
title = "Large deviations for increasing subsequences of permutations and a concurrency application",
abstract = "The study of concurrent processes with conflicts aecting concurrent execution has been long related to various geometric objects. In the special case of two processes and non-overlapping conflicts (definitions below) an instance of a problem is encoded by a permutation describing the conflict sets for the interacting processes. Further, it turns out that the set of increasing subsequences of the permutation describes the homotopy classes of the execution plans for the concurrent processes, an abstraction encoding 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 delay either process's access to shared resources 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. Finally, we indicate how our results generalize to larger numbers of processes, wherein conflict sets may take on more interesting geometries.",
keywords = "Increasing subsequences, Large deviations, Permutations",
author = "Yuliy Baryshnikov and Abram Magner",
year = "2018",
month = "3",
day = "20",
doi = "10.1145/3199524.3199538",
language = "English (US)",
volume = "45",
pages = "84--89",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

TY - JOUR

T1 - Large deviations for increasing subsequences of permutations and a concurrency application

AU - Baryshnikov, Yuliy

AU - Magner, Abram

PY - 2018/3/20

Y1 - 2018/3/20

N2 - The study of concurrent processes with conflicts aecting concurrent execution has been long related to various geometric objects. In the special case of two processes and non-overlapping conflicts (definitions below) an instance of a problem is encoded by a permutation describing the conflict sets for the interacting processes. Further, it turns out that the set of increasing subsequences of the permutation describes the homotopy classes of the execution plans for the concurrent processes, an abstraction encoding 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 delay either process's access to shared resources 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. Finally, we indicate how our results generalize to larger numbers of processes, wherein conflict sets may take on more interesting geometries.

AB - The study of concurrent processes with conflicts aecting concurrent execution has been long related to various geometric objects. In the special case of two processes and non-overlapping conflicts (definitions below) an instance of a problem is encoded by a permutation describing the conflict sets for the interacting processes. Further, it turns out that the set of increasing subsequences of the permutation describes the homotopy classes of the execution plans for the concurrent processes, an abstraction encoding 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 delay either process's access to shared resources 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. Finally, we indicate how our results generalize to larger numbers of processes, wherein conflict sets may take on more interesting geometries.

KW - Increasing subsequences

KW - Large deviations

KW - Permutations

UR - http://www.scopus.com/inward/record.url?scp=85046630092&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046630092&partnerID=8YFLogxK

U2 - 10.1145/3199524.3199538

DO - 10.1145/3199524.3199538

M3 - Conference article

AN - SCOPUS:85046630092

VL - 45

SP - 84

EP - 89

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 3

ER -