On the space complexity of randomized synchronization

No abstract is available for this paper.

• Publication year

  1993

• Venue

  ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

• Publication date

  1993-09-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/164051.164078
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computing with faulty shared objects

  1995cited by this paper
• Synchronization power depends on the register size

  1993cited by this paper
• Practical considerations for non-blocking concurrent objects

  1993cited by this paper
• Distributed Algorithms

  1992cited by this paper
• Fault-tolerant wait-free shared objects

  1992cited by this paper
• Performance issues in non-blocking synchronization on shared-memory multiprocessors

  1992cited by this paper
• Concurrent counting

  1992influential reference
• Time-Lapse Snapshots

  1992cited by this paper
• Time-and Space-eecient Randomized Consensus

  1992cited by this paper
• Randomized consensus in expected O(n log/sup 2/ n) operations per processor

  1992cited by this paper
• Randomized Consensus in Expected O(n²log n) Operations

  1991cited by this paper
• Practical considerations for lock-free concurrent objects

  1991cited by this paper
• Optimal time randomized consensus—making resilient algorithms fast in practice

  1991cited by this paper
• Randomized wait-free concurrent objects (extended abstract)

  1991cited by this paper
• Wait-free synchronization

  1991influential reference
• Fast Randomized Consensus Using Shared Memory

  1990cited by this paper
• Linearizability: a correctness condition for concurrent objects

  1990cited by this paper
• Atomic snapshots of shared memory

  1990cited by this paper
• Time-and space-efficient randomized consensus

  1990cited by this paper
• On the improbability of reaching Byzantine agreements

  1989cited by this paper
• Bounded polynomial randomized consensus

  1989cited by this paper
• On achieving consensus using a shared memory

  1988cited by this paper
• Hierarchical correctness proofs for distributed algorithms

  1987cited by this paper
• On processor coordination using asynchronous hardware

  1987cited by this paper
• On the minimal synchronism needed for distributed consensus

  1983cited by this paper
• Mutual exclusion using indivisible reads and writes

  1980cited by this paper

• Solving Tasks with Fewer Registers Than Processes

  2025cites this paper
• Fault-tolerant computing with unreliable channels

  2023cites this paper
• Agreeing within a few writes

  2022cites this paper
• Optimal Resilience in Systems that Mix Shared Memory and Message Passing

  2020cites this paper
• Linear Space Boostrap Communication Scheme

  2019cites this paper
• On the uncontended complexity of anonymous agreement

  2017cites this paper
• Lower Bound on the Step Complexity of Anonymous Binary Consensus

  2016cites this paper
• Networked Systems

  2016influential citation
• D C ] 1 9 M ar 2 01 6 On the Space Complexity of Renaming

  2016cites this paper
• Brief Announcement: A Tight Space Bound for Consensus

  2016cites this paper
• Lower and upper bounds for single-scanner snapshot implementations

  2016cites this paper
• Lower Bounds for Restricted-Use Objects

  2016cites this paper
• Anonymity-Preserving Failure Detectors

  2016cites this paper
• 13 M ar 2 01 6 On the Space Complexity of Renaming

  2016cites this paper
• A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

  2016cites this paper
• Étude de la complexité des implémentations d'objets concurrents, sans attente, abandonnables et/ou solo-rapides

  2016cites this paper
• A tight space bound for consensus

  2016cites this paper
• On the optimal space complexity of consensus for anonymous processes

  2015influential citation
• Brief Announcement: Tight Space Bounds for Memoryless Anonymous Consensus

  2015cites this paper
• A Quarter-Century of Wait-Free Synchronization

  2015cites this paper
• On the Space Complexity of Set Agreement

  2015influential citation
• Fault-tolerant Distributed Systems in Hardware

  2015cites this paper
• On the Time and Space Complexity of ABA Prevention and Detection

  2015cites this paper
• On the Uncontended Complexity of Anonymous Consensus

  2015cites this paper
• Anonymous obstruction-free (n, k)-set agreement with n-k+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-k+1$$\end{

  2015cites this paper
• Tight Space Bounds for Memoryless Anonymous Consensus Leqi Zhu

  2015cites this paper
• Anonymous Obstruction-free $(n,k)$-Set Agreement with $n-k+1$ Atomic Read/Write Registers

  2015cites this paper
• Impossibility Results for Distributed Computing

  2014cites this paper
• Solo-Fast Universal Constructions for Deterministic Abortable Objects

  2014cites this paper
• Tight Bounds for Adopt-Commit Objects

  2014cites this paper
• Communication-efficient randomized consensus

  2014cites this paper
• Notes on Theory of Distributed Systems

  2014cites this paper
• Allocation adaptative de registres en utilisant un nombre linéaire de registres

  2014cites this paper
• Snapshot Isolation Does Not Scale Either

  2013cites this paper
• On deterministic abortable objects

  2013cites this paper
• Adaptive Register Allocation with a Linear Number of Registers

  2013cites this paper
• An O ( √ n ) Space Bound for Obstruction-Free Leader Election

  2013cites this paper
• Lower bounds for restricted-use objects: extended abstract

  2012cites this paper
• RMR-efficient implementations of comparison primitives using read and write operations

  2012cites this paper
• On the time and space complexity of randomized test-and-set

  2012cites this paper
• On the Inherent Sequentiality of Concurrent Objects

  2012cites this paper
• Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated

  2011cites this paper
• Tight bounds for anonymous adopt-commit objects

  2011cites this paper
• The Space Complexity of Long-Lived and One-Shot Timestamp Implementations

  2011cites this paper
• The space complexity of long-lived and one-shot timestamp implementations

  2011cites this paper
• The Complexity of Obstruction-Free Implementations

  2009cites this paper
• Abortable and Query-abortable Types and Their Efficient Implementation

  2009cites this paper
• Bounded-Bypass Mutual Exclusion with Minimum Number of Registers

  2009cites this paper
• The complexity of obstruction-free implementations

  2009cites this paper
• The Cost of Obstruction-Freedom ∗

  2007cites this paper
• Time lower bounds for implementations of multi-writer snapshots

  2007cites this paper
• The space complexity of unbounded timestamps

  2007cites this paper
• Time-space tradeoffs for implementations of snapshots

  2006cites this paper
• Reconciling nondeterministic and probabilistic choices

  2006cites this paper
• The complexity of updating multi-writer snapshot objects

  2006cites this paper
• Synchronizing without locks is inherently expensive

  2006cites this paper
• Linear lower bounds on real-world implementations of concurrent objects

  2005cites this paper
• A fair and space-efficient mutual exclusion

  2005cites this paper
• Computing with Reads and Writes in the Absence of Step Contention

  2005cites this paper
• Lower bounds for adaptive collect and related objects

  2004cites this paper
• A tight time lower bound for space-optimal implementations of multi-writer snapshots

  2003influential citation
• Uniform Solvability with a Finite Number of MWMR Registers

  2003influential citation
• On the Uncontended Complexity of Consensus

  2003cites this paper
• Resilient Consensus for Infinitely Many Processes

  2003cites this paper
• On the Complexity of Implementing Certain Classes of Shared Objects

  2003cites this paper
• Tight bounds for shared memory systems accessed by Byzantine processes

  2002cites this paper
• Wait-free consensus with infinite arrivals

  2002cites this paper
• Space-optimal multi-writer snapshot objects are slow

  2002cites this paper
• Fairness of Shared Objects

  1998influential citation
• Computing in Totally Anonymous Asynchronous Shared Memory Systems

  1998influential citation
• A time complexity lower bound for randomized implementations of some shared objects

  1998cites this paper
• Lower bounds for distributed coin-flipping and randomized consensus

  1998cites this paper
• Lower bounds for distributed coin-flipping and randomized consensus

  1997cites this paper
• Computability and complexity results for agreement problems in shared memory distributed systems

  1996influential citation
• Time and space lower bounds for non-blocking implementations (preliminary version)

  1996cites this paper
• Failure detectors and the wait-free hierarchy (extended abstract)

  1995cites this paper
• Using Failure Detectors to Solve Consensus in Asynchronous Sharde-Memory Systems (Extended Abstract)

  1994cites this paper
• Generalized Agreement Between Concurrent Fail-Stop Processes

  1993cites this paper
• Resilient Consensus for Infinitely Many Processes

  year unknowncites this paper