Affordable Access

Publisher Website

On the time complexity of minimum and maximum global snapshot problems

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
67
Issue
3
Identifiers
DOI: 10.1016/s0020-0190(98)00100-8
Keywords
  • Distributed Systems
  • Computational Complexity
  • Error Detection
  • Global Snapshot

Abstract

Abstract Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj, Chen and Wu, have shown that the minimum and maximum global snapshot problems are linear-time reducible to the maximum constant-ratio network flow (MCNF) problem, here defined as the wellknown maximum network flow problem with m = Θ( n), where m is the number of edges and n is the number of vertices in the given flow network. In this paper we show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, we can conclude that the global snapshot problems are “as difficult as” the MCNF problem in terms of time complexity.

There are no comments yet on this publication. Be the first to share your thoughts.