A Class of Optimal Decentralized Commit Protocols.

Abstract

This paper studies the message complexity of decentralized commit protocols. It shows that Theta (kNN to the 1/k power) messages are necessary only if k rounds of message interchanges are allowed. It also shows that Theta (n1nN) is a message lower bound for any decentralized commit protocol. Finally, a class of decentralized commit protocols are proposed which need Theta (kNN to the 1/k power) messages and use k rounds of message interchanges. If we let k=1nN then we can get a decentralized commit protocol which needs Theta (N1nN) messages only.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA183373

Entities

People

  • Ashok Agrawala
  • Shyan-ming Yuan

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Abstracts
  • Availability
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Maryland
  • Military Research
  • Monitoring
  • Multithreading
  • Security
  • Transitions
  • Universities

Fields of Study

  • Computer science

Readers

  • Analytical Mechanics
  • Computer Networking