Automatically assigned DDC number: 00436
Manually assigned DDC number: 00435

Number of references: 8

Title: Time/Contention Trade-offs for Multiprocessor Synchronization

Author:

Author:

Subject: James H. Anderson,Jae-heon Yang Time/Contention Trade-offs for Multiprocessor Synchronization

Description: We establish trade-offs between time complexity and write- and access-contention for solutions to the mutual exclusion problem. The write-contention (access-contention) of a concurrent program is the number of processes that may be simultaneously enabled to write (access by reading and/or writing) the same shared variable. Our notion of time complexity distinguishes between local and remote accesses of shared memory. We show that, for any N-process mutual exclusion algorithm, if write-contention is w, and if at most v remote variables can be accessed by a single atomic operation, then there exists an execution involving only one process in which that process executesOmegaGammaecu vw N) remote operations for entry into its critical section. We further show that, among these operations,OmegaGamma p log vw N) distinct remote variables are accessed. For algorithms with access-contention c, we show that the latter bound can be improved to OmegaGamma/51 vc N ). The last two of thes...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1995-07-24

Pubyear: 1996

Format: ps

Identifier: http://citeseer.ist.psu.edu/167770.html

Source: http://www.cs.unc.edu/~anderson/papers/iandc95.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/35710.html" Type="article" CiteSeer_Book="ACTAINF Acta Informatica" CiteSeer_Volume="30" Title="A Fine-grained Solution to the Mutual Exclusion Problem,">

<identifier Org="ISBN:0131972596" Paper_ID="/35710.html" Extracted="0131972596" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897916131" Paper_ID="/35710.html" Extracted="0897916131" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897916638" Paper_ID="/35710.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:1581134851" Paper_ID="/35710.html" Extracted="1581134851" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:1595933840" Paper_ID="/35710.html" Extracted="1595933840" />

<identifier Org="ISBN:3540233067" Paper_ID="/35710.html" Extracted="3540233067" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540561889" Paper_ID="/35710.html" Extracted="3540561889" DDC="004/.36/015118" Normalized_DDC="00436015118" Normalized_Weight="0.16666666666666666" />

</rec>

<rec ID="/570102.html" Type="article" CiteSeer_Book="Information and Computation" CiteSeer_Volume="107" Title="Bounds on Shared Memory for Mutual Exclusion,">

<identifier Org="ISBN:0131972596" Paper_ID="/570102.html" Extracted="0131972596" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0387301623" Paper_ID="/570102.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0521876346" Paper_ID="/570102.html" Extracted="0521876346" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0769522815" Paper_ID="/570102.html" Extracted="0769522815" />

<identifier Org="ISBN:1581131836" Paper_ID="/570102.html" Extracted="1581131836" />

<identifier Org="ISBN:1581134851" Paper_ID="/570102.html" Extracted="1581134851" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:1581136749" Paper_ID="/570102.html" Extracted="1581136749" />

<identifier Org="ISBN:1581138024" Paper_ID="/570102.html" Extracted="1581138024" />

<identifier Org="ISBN:354020184X" Paper_ID="/570102.html" Extracted="354020184X" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540233067" Paper_ID="/570102.html" Extracted="3540233067" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540291636" Paper_ID="/570102.html" Extracted="3540291636" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540411437" Paper_ID="/570102.html" Extracted="3540411437" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:354043996X" Paper_ID="/570102.html" Extracted="354043996X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540650660" Paper_ID="/570102.html" Extracted="3540650660" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540751416" Paper_ID="/570102.html" Extracted="3540751416" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540787992" Paper_ID="/570102.html" Extracted="3540787992" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />

</rec>

<rec ID="/49819.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Contention in shared memory algorithms,">

<identifier Org="ISBN:0387986804" Paper_ID="/49819.html" Extracted="0387986804" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0769522815" Paper_ID="/49819.html" Extracted="0769522815" />

<identifier Org="ISBN:0818676833" Paper_ID="/49819.html" Extracted="0818676833" DDC="004.35" Normalized_DDC="00435" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897915917" Paper_ID="/49819.html" Extracted="0897915917" />

<identifier Org="ISBN:0897916131" Paper_ID="/49819.html" Extracted="0897916131" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897916638" Paper_ID="/49819.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897917103" Paper_ID="/49819.html" Extracted="0897917103" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897918002" Paper_ID="/49819.html" Extracted="0897918002" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897919068" Paper_ID="/49819.html" Extracted="0897919068" DDC="005.2/75" Normalized_DDC="005275" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897919521" Paper_ID="/49819.html" Extracted="0897919521" />

<identifier Org="ISBN:1581137087" Paper_ID="/49819.html" Extracted="1581137087" />

<identifier Org="ISBN:1581138024" Paper_ID="/49819.html" Extracted="1581138024" />

<identifier Org="ISBN:1584884355" Paper_ID="/49819.html" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540411437" Paper_ID="/49819.html" Extracted="3540411437" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540572716" Paper_ID="/49819.html" Extracted="3540572716" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540584498" Paper_ID="/49819.html" Extracted="3540584498" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540616276" Paper_ID="/49819.html" Extracted="3540616276" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.08333333333333333" />

</rec>

<rec ID="/750.html" Type="article" CiteSeer_Book="ACM Transactions on Programming Languages and Systems" CiteSeer_Volume="13" Title="Wait-Free Synchronization,">

<identifier Org="ISBN:0131972596" Paper_ID="/750.html" Extracted="0131972596" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.1" />

<identifier Org="ISBN:0201310090" Paper_ID="/750.html" Extracted="0201310090" DDC="005.2/752" Normalized_DDC="0052752" Normalized_Weight="0.1" />

<identifier Org="ISBN:047143230X" Paper_ID="/750.html" Extracted="047143230X" DDC="005.2/75" Normalized_DDC="005275" Normalized_Weight="0.1" />

<identifier Org="ISBN:0780357973" Paper_ID="/750.html" Extracted="0780357973" />

<identifier Org="ISBN:0897916131" Paper_ID="/750.html" Extracted="0897916131" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:0897919521" Paper_ID="/750.html" Extracted="0897919521" />

<identifier Org="ISBN:1581130996" Paper_ID="/750.html" Extracted="1581130996" />

<identifier Org="ISBN:1581137087" Paper_ID="/750.html" Extracted="1581137087" />

<identifier Org="ISBN:1581138024" Paper_ID="/750.html" Extracted="1581138024" />

<identifier Org="ISBN:188044609X" Paper_ID="/750.html" Extracted="188044609X" />

<identifier Org="ISBN:1880446766" Paper_ID="/750.html" Extracted="1880446766" />

<identifier Org="ISBN:3540437592" Paper_ID="/750.html" Extracted="3540437592" DDC="005.1/17" Normalized_DDC="005117" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540561889" Paper_ID="/750.html" Extracted="3540561889" DDC="004/.36/015118" Normalized_DDC="00436015118" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540572716" Paper_ID="/750.html" Extracted="3540572716" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540602747" Paper_ID="/750.html" Extracted="3540602747" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540650660" Paper_ID="/750.html" Extracted="3540650660" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540751416" Paper_ID="/750.html" Extracted="3540751416" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

</rec>

<rec ID="/389559.html" Type="article" CiteSeer_Book="ACM Transactions on Computer Systems" CiteSeer_Volume="5" Title="A Fast Mutual Exclusion Algorithm,">

<identifier Org="ISBN:0131972596" Paper_ID="/389559.html" Extracted="0131972596" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0387301623" Paper_ID="/389559.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0471453242" Paper_ID="/389559.html" Extracted="0471453242" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0818631953" Paper_ID="/389559.html" Extracted="0818631953" />

<identifier Org="ISBN:0818642211" Paper_ID="/389559.html" Extracted="0818642211" />

<identifier Org="ISBN:0897916638" Paper_ID="/389559.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:1402081405" Paper_ID="/389559.html" Extracted="1402081405" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:1581130996" Paper_ID="/389559.html" Extracted="1581130996" />

<identifier Org="ISBN:1581131836" Paper_ID="/389559.html" Extracted="1581131836" />

<identifier Org="ISBN:1581133839" Paper_ID="/389559.html" Extracted="1581133839" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:1581134851" Paper_ID="/389559.html" Extracted="1581134851" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:354020184X" Paper_ID="/389559.html" Extracted="354020184X" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:354024302X" Paper_ID="/389559.html" Extracted="354024302X" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540411437" Paper_ID="/389559.html" Extracted="3540411437" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540426051" Paper_ID="/389559.html" Extracted="3540426051" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:354043996X" Paper_ID="/389559.html" Extracted="354043996X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540665315" Paper_ID="/389559.html" Extracted="3540665315" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540877789" Paper_ID="/389559.html" Extracted="3540877789" />

<identifier Org="ISBN:8126509163" Paper_ID="/389559.html" Extracted="8126509163" />

</rec>

<rec ID="/517911.html" Type="article" CiteSeer_Book="ACM Transactions on Computer Systems" CiteSeer_Volume="11" Title="Waiting Algorithms for Synchronization in Large-Scale Multiprocessors,">

<identifier Org="ISBN:0792394771" Paper_ID="/517911.html" Extracted="0792394771" DDC="004/.32" Normalized_DDC="00432" Normalized_Weight="0.25" />

<identifier Org="ISBN:0818638109" Paper_ID="/517911.html" Extracted="0818638109" DDC="004.2/2" Normalized_DDC="00422" Normalized_Weight="0.25" />

<identifier Org="ISBN:0818650508" Paper_ID="/517911.html" Extracted="0818650508" />

<identifier Org="ISBN:0818664452" Paper_ID="/517911.html" Extracted="0818664452" DDC="004.2/2" Normalized_DDC="00422" Normalized_Weight="0.25" />

<identifier Org="ISBN:1581130996" Paper_ID="/517911.html" Extracted="1581130996" />

<identifier Org="ISBN:1581138407" Paper_ID="/517911.html" Extracted="1581138407" />

<identifier Org="ISBN:3540618643" Paper_ID="/517911.html" Extracted="3540618643" DDC="005.4/3" Normalized_DDC="00543" Normalized_Weight="0.25" />

</rec>

<rec ID="/78985.html" Type="inproceedings" CiteSeer_Book="Proceeding of the 12th Annual ACM Symposium on Principles of Distributed Computing PODC 93" CiteSeer_Volume="" Title="Fast, Scalable Synchronization with Minimal Hardware Support,">

<identifier Org="ISBN:0126339511" Paper_ID="/78985.html" Extracted="0126339511" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.1" />

<identifier Org="ISBN:0131972596" Paper_ID="/78985.html" Extracted="0131972596" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818676833" Paper_ID="/78985.html" Extracted="0818676833" DDC="004.35" Normalized_DDC="00435" Normalized_Weight="0.1" />

<identifier Org="ISBN:0897916131" Paper_ID="/78985.html" Extracted="0897916131" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:0897916638" Paper_ID="/78985.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.1" />

<identifier Org="ISBN:0897917170" Paper_ID="/78985.html" Extracted="0897917170" DDC="004.22" Normalized_DDC="00422" Normalized_Weight="0.1" />

<identifier Org="ISBN:1581133839" Paper_ID="/78985.html" Extracted="1581133839" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540233067" Paper_ID="/78985.html" Extracted="3540233067" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540584498" Paper_ID="/78985.html" Extracted="3540584498" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540665315" Paper_ID="/78985.html" Extracted="3540665315" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.1" />

</rec>

<rec ID="/110389.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Time bounds for mutual exclusion and related problems,">

<identifier Org="ISBN:0131972596" Paper_ID="/110389.html" Extracted="0131972596" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.2" />

<identifier Org="ISBN:0897916638" Paper_ID="/110389.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.2" />

<identifier Org="ISBN:0897917170" Paper_ID="/110389.html" Extracted="0897917170" DDC="004.22" Normalized_DDC="00422" Normalized_Weight="0.2" />

<identifier Org="ISBN:3540411437" Paper_ID="/110389.html" Extracted="3540411437" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.2" />

<identifier Org="ISBN:3540584498" Paper_ID="/110389.html" Extracted="3540584498" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.2" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Time/Contention Trade-offs for Multiprocessor Synchronization">

<identifier Org="ISBN:1581131836" Paper_ID="SELF" Extracted="1581131836" />

<identifier Org="ISBN:1581134851" Paper_ID="SELF" Extracted="1581134851" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.5" />

<identifier Org="ISBN:1581136749" Paper_ID="SELF" Extracted="1581136749" />

<identifier Org="ISBN:1581137087" Paper_ID="SELF" Extracted="1581137087" />

<identifier Org="ISBN:1584884355" Paper_ID="SELF" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.5" />

<identifier Org="ISBN:1595933840" Paper_ID="SELF" Extracted="1595933840" />

</rec>

</references_metadata>