NDLI: Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Please wait, while we are loading the content...

New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

Analysing Snapshot Isolation

Deterministic Objects: Life Beyond Consensus

Concurrent Data Structures

Contention Resolution on a Fading Channel

Distributed Strong Diameter Network Decomposition: Extended Abstract

Space Bounds for Reliable Storage: Fundamental Limits of Coding

How Emerging Memory Technologies Will Have You Rethinking Algorithm Design

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

A Faster Distributed Radio Broadcast Primitive: Extended Abstract

Search on a Line with Faulty Robots

Low-Congestion Shortcuts without Embedding

The Greedy Spanner is Existentially Optimal

Recoverable Mutual Exclusion: [Extended Abstract]

Unbeatable Set Consensus via Topological and Combinatorial Reasoning

Reliable Communication over Highly Connected Noisy Networks

Optimal Dynamic Distributed MIS

Specification and Complexity of Collaborative Text Editing

On the Complexity of Reader-Writer Locks: Extended Abstract

Broadcast Extensions with Optimal Communication and Round Complexity

Uniform Deployment of Mobile Agents in Asynchronous Rings

The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process

MST in Log-Star Rounds of Congested Clique

A Randomized Concurrent Algorithm for Disjoint Set Union

A Polylogarithmic Gossip Algorithm for Plurality Consensus

Contention Resolution on Multiple Channels with Collision Detection

A Local Constant Factor MDS Approximation for Bounded Genus Graphs

Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract

An Algorithm for Replicated Objects with Efficient Reads

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Ant-Inspired Density Estimation via Random Walks: Extended Abstract

Distributed Algorithms for Planar Networks I: Planar Embedding

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]

Noisy Rumor Spreading and Plurality Consensus

How Asynchrony Affects Rumor Spreading Time

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract

A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

Are Shared Objects Composable under an Oblivious Adversary?

How Proofs are Prepared at Camelot: Extended Abstract

Brief Announcement: Active Information Spread in Networks

Brief Announcement: Multi-Broadcasting under the SINR Model

Brief Announcement: Labeling Schemes for Power-Law Graphs

Brief Announcement: Local Independent Set Approximation

Rational Consensus: Extended Abstract

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

Brief Announcement: Certified Universal Gathering in $R^{2}$ for Oblivious Mobile Robots

Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs

Brief Announcement: A Tight Space Bound for Consensus

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks

Brief Announcement: Asynchronous Coordination with Constraints and Preferences

Brief Announcement: Computing in the Presence of Weak Crash Failures

Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation

Brief Announcement: A Key-Value Map for Massive Real-Time Analytics

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks

Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries

Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory

Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space

Brief Announcement: The Small World of Curious Beings

Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

Brief Announcement: Space-Time Tradeoffs for Distributed Verification

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Content Provider	ACM Digital Library
Author	Raynal, Michel Mostefaoui, Achour
Abstract	Atomic registers are certainly the most basic objects of computing science. Their implementation on top of an n-process asynchronous message-passing system has received a lot of attention. It has been shown that t < n/2 (where t is the maximal number of processes that may crash) is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. Considering such a context, this paper presents an algorithm which implements a single-writer multi-reader atomic register with four message types only, and where no message needs to carry control information in addition to its type. Hence, two bits are sufficient to capture all the control information carried by all the implementation messages. Moreover, the messages of two types need to carry a data value while the messages of the two other types carry no value at all. As far as we know, this algorithm is the first with such a sufficiency property on the size of control information carried by messages. It is also particularly efficient from a time complexity point of view.
Starting Page	381
Ending Page	389
Page Count	9
File Format	PDF
ISBN	9781450339643
DOI	10.1145/2933057.2933095
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Upper bound Asynchronous message-passing system Atomic read-write register Message type Process crash failure Sequence number Reliability Algorithm
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in