A Symmetric O(n log n) Message Distributed Snapshot Algorithm for Large-Scale Systems

被引：0
|
作者：
Kshemkalyani, Ajay D. [1 ]
机构：
[1] Univ Illinois, Dept Comp Sci, Chicago, IL 60607 USA
来源：
2009 IEEE INTERNATIONAL CONFERENCE ON CLUSTER COMPUTING AND WORKSHOPS | 2009年
关键词：
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper presents a O(n log n) message distributed snapshot algorithm for a system with non-FIFO channels, where n is the number of processors. The algorithm finds applications for checkpointing in large scale supercomputers and distributed systems that have a fully connected logical topology over a large number of processors. Each processor sends log n messages in the algorithm. The sizes of the messages are geometrically distributed, and the sum of the sizes of the messages sent by any processor is n. The response time of the algorithm is O(log n). The algorithm is fully distributed and the role of each processor is symmetric, unlike tree-based, ring-based, and centralized algorithms.
引用
收藏
页码：597 / 600
页数：4
相关论文
共 50 条
  • [21] An O(log n log log n) space algorithm for undirected st-connectivity
    Trifonov, Vladimir
    SIAM JOURNAL ON COMPUTING, 2008, 38 (02) : 449 - 483
  • [22] An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Asadpour, Arash
    Goemans, Michel X.
    Madry, Aleksander
    Gharan, Shayan Oveis
    Saberi, Amin
    OPERATIONS RESEARCH, 2017, 65 (04) : 1043 - 1061
  • [23] EpTO: An Epidemic Total Order Algorithm for Large-Scale Distributed Systems
    Matos, Miguel
    Mercier, Hugues
    Felber, Pascal
    Oliveira, Rui
    Pereira, Jose
    PROCEEDINGS OF THE 16TH ANNUAL MIDDLEWARE CONFERENCE, 2015, : 100 - 111
  • [24] An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Asadpour, Arash
    Goemans, Michel X.
    Madry, Aleksander
    Gharan, Shayan Oveis
    Saberi, Amin
    PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2010, 135 : 379 - +
  • [25] Low Complexity Message Passing Detection Algorithm for Large-Scale MIMO Systems
    Zeng, Jing
    Lin, Jun
    Wang, Zhongfeng
    IEEE WIRELESS COMMUNICATIONS LETTERS, 2018, 7 (05) : 708 - 711
  • [26] An optimal distributed trigger counting algorithm for large-scale networked systems
    Kim, Seokhyun
    Lee, Jaeheung
    Park, Yongsu
    Cho, Yookun
    SIMULATION-TRANSACTIONS OF THE SOCIETY FOR MODELING AND SIMULATION INTERNATIONAL, 2013, 89 (07): : 846 - 859
  • [27] An Efficient Distributed Algorithm for Resource Allocation in Large-Scale Coupled Systems
    Niu, Di
    Li, Baochun
    2013 PROCEEDINGS IEEE INFOCOM, 2013, : 1501 - 1509
  • [28] Reduced Complexity Message Passing Detection Algorithm in Large-Scale MIMO Systems
    Zhu, Haochuan
    Lin, Jun
    Wang, Zhongfeng
    2017 9TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS AND SIGNAL PROCESSING (WCSP), 2017,
  • [29] Towards a practical O(n log n) phylogeny algorithm
    Truszkowski, Jakub
    Hao, Yanqi
    Brown, Daniel G.
    ALGORITHMS FOR MOLECULAR BIOLOGY, 2012, 7
  • [30] An O(M(n) log n) Algorithm for the Jacobi Symbol
    Brent, Richard P.
    Zimmermann, Paul
    ALGORITHMIC NUMBER THEORY, 2010, 6197 : 83 - +
12345