Publication

COMBINE: An Improved Directory-Based Consistency Protocol

Vincent Gramoli, Hagit Albo Attiya
2010
Report or working paper
Abstract

This paper presents COMBINE, a directory-based consistency protocol for shared objects, designed for large-scale distributed systems with unreliable links. Directory-based consistency protocols support move requests, allowing to write the object locally, as well as lookup requests, providing a read-only copy of the object. They have been used in distributed shared memory implementations and are a key element of data-flow implementations of distributed software transactional memory in large-scale systems. The protocol runs on an overlay tree, whose leaves are the nodes of the system, and its main novelty is in combining requests that overtake each other as they pass through the same node. Combining requests on a simple tree structure allows the protocol to tolerate non-fifo links and handle concurrent requests. Combining also avoids race conditions and ensures that the cost of serving a request is proportional to the cost of the shortest path between the requesting node and the serving node, in the overlay tree. Using an overlay tree with a good stretch factor yields an efficient protocol.

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 Chatbot

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.