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>

www.000webhost.com