Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Resource Bounds and Combinations of Consensus Objects

Resource Bounds and Combinations of Consensus Objects

File(s)
93-1351.ps (190.26 KB)
93-1351.pdf (1.68 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6121
Collections
Computer Science Technical Reports
Author
Kleinberg, Jon M.
Mullainathan, Sendhil
Abstract

The shared-memory model of computation typically provides processes with an arbitrary number of copies of the available object types; yet a simple argument shows that any consensus protocol can only make use of some finite subset of these. Thus we believe it is useful to consider the problem of consensus from the point of view of resource bounds, determining whether consensus can still be solved when the number of copies of the system's shared objects is limited. This approach leads to a general technique which we call the combination protocol, in which the number of processes that can achieve consensus with a given object increases as more copies of it are made available. Such a phenomenon brings up questions about the robustness of Herlihy's consensus hierarchy, in that objects are being combined to solve $n$-process consensus, even though no single copy can do so individually. We show how the ideas in the combination protocol appear even in situations where objects are not explicitly being combined with one another; we also consider the general question of resource bounds in several known consensus protocols. We analyze two such protocols that use seemingly similar primitives, achieving a substantial improvement in one case and showing a tight lower bound in the other.

Date Issued
1993-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1351
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance