Technical Report CS-2012-07

Title: Hybrid Distributed Consensus
Authors: Roy Friedman, Gabriel Kliot, and
Abstract: Inspired by the proliferation of cloud-based services, this paper studies consensus, one of the most fundamental distributed computing problems, in a hybrid model of computation. In this model, processes (or nodes) exchange information by passing messages or by accessing a reliable and highly-available register hosted in the cloud. The paper presents a formal definition of the model and problem, and studies performance tradeoffs related to using such a register. Specifically, it proves a lower bound on the number of register accesses in deterministic protocols, and gives a simple deterministic protocol that meets this bound. In addition, probabilistic protocols that solve consensus with a single register access in expectation or when some favorable network conditions occur are also presented. A benefit of the probabilistic approach is that it can ensure both liveness and safety, and only the efficiency of the protocol is affected by the probabilistic assumptions.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2012
To the main CS technical reports page

Computer science department, Technion