QoS-Aware and Fault-Tolerant Replica Placement

Jingkun Hu, Zhihui Du, Sen Zhang, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


As emerging applications become more and more distributed and decentralized, it has become a more challenging problem to design and build fault-tolerant network systems with high Quality of Service (QoS) guarantee. In this paper, an optimal replica placement problem is formulated in terms of minimizing the replica placement cost subject to both QoS and fault-tolerant constraints. Based on the generalized graph model, the optimal replica placement problem is proved to be NP-hard. The essential properties of the proposed problem are investigated and two criteria, which can quantitatively measure the replica demand of each node and the contribution of one replica to other nodes in the graph, are proposed. The criteria are employed to develop efficient heuristic algorithms. Finally the proposed algorithms are evaluated with extensive network configurations and the experimental results show that the proposed heuristic algorithms can generate solutions very close to the optimal results.

Original languageEnglish (US)
Title of host publicationAlgorithms and Architectures for Parallel Processing - 20th International Conference, ICA3PP 2020, Proceedings
EditorsMeikang Qiu
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages16
ISBN (Print)9783030602383
StatePublished - 2020
Event20th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2020 - New York, United States
Duration: Oct 2 2020Oct 4 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12453 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2020
Country/TerritoryUnited States
CityNew York

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Distributed system
  • Fault tolerance
  • Heuristic algorithm
  • Quality of service
  • Replica placement


Dive into the research topics of 'QoS-Aware and Fault-Tolerant Replica Placement'. Together they form a unique fingerprint.

Cite this