Publication

How Fast can a Distributed Atomic Read be?

Rachid Guerraoui, Partha Dutta
2005
Reports

Abstract

We study efficient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as failure prone server processes implementing the data structure. We determine the exact conditions under which every read operation involves one-round of communication with the servers. These conditions relate the number of readers to the tolerated number of faulty servers, in a general model with crash and arbitrary failures.

Official source

https://infoscience.epfl.ch/entities/publication/3700ebb9-7ee5-454e-a474-88b7529b028c

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Rachid Guerraoui, Partha Dutta
2005
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/3700ebb9-7ee5-454e-a474-88b7529b028c

About this result

Related concepts (22)

Persistent data structure

In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjans' 1986 article. A data structure is partially persistent if all versions can be accessed but only the newest version can be modified.

Distributed computing

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. Distributed computing is a field of computer science that studies distributed systems. The components of a distributed system interact with one another in order to achieve a common goal. Three significant challenges of distributed systems are: maintaining concurrency of components, overcoming the lack of a global clock, and managing the independent failure of components.

Paxos (computer science)

Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures. Consensus protocols are the basis for the state machine replication approach to distributed computing, as suggested by Leslie Lamport and surveyed by Fred Schneider.

Related publications (2)

How Fast can a Distributed Atomic Read be?

Chat with Graph Search

Spores, Formally

Indulgent Algorithms