Distributed Algorithm Engineering for the Era of Tera

Tera时代的分布式算法工程

• 批准号: 18300004
• 负责人: YAMASHITA Masafumi
• 金额: $ 8.07万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18300004/
• 关键词: 巨大分散システム; 安定性; 分子計算; 複雑ネットワーク; センサ・ネットワーク; 分散アルゴリズム; センサーネットワーク; WWW; 安定性・信頼性; 進化ネットワーク

The main purpose of this project is to construct a design theory of distributed algorithms for huge distributed systems. From the view of guaranteeing the stability of such distributed systems, we have investigated probabilistic distributed algorithms and self-stabilizing algorithms and obtained results, a part of which are listed in Section 5. I also wrote a textbook entitled ``Adaptive Distributed Algorithms'' co-authored with Prof. Masuzawa, which is the first textbook in this field.

本课题的主要目的是为大型分布式系统构建分布式算法的设计理论。从保证分布式系统稳定性的角度出发，我们研究了概率分布式算法和自稳定算法，并得到了一些结果，部分结果在第5节中列出。我还与Masuzawa教授合作编写了一本名为《Adaptive Distributed Algorithms》的教科书，这是该领域的第一本教科书。

项目成果

How to Design a Linear Cover Time Random Walk on a Finite Graph

如何设计有限图上的线性覆盖时间随机游走

• DOI: 10.1007/978-3-642-04944-6_9
• 发表时间: 2009
• 期刊: SAGA
• 作者: Yoshiaki Nonaka;Hirotaka Ono;Kunihiko Sadakane;Masafumi Yamashita
• 通讯作者: Masafumi Yamashita

A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems

一种近似求解随机图优化问题的通用算法

• 发表时间: 2009
• 作者: E.Ando;et al.
• 通讯作者: et al.

An Exact Algorithm for the Stochastic Longest Path Problem in a DAG

有向无环图随机最长路径问题的精确算法

• 发表时间: 2009
• 作者: E.Ando;et al.
• 通讯作者: et al.

任意のカバー時間のランダムウォークを持つ木の構成法

任意覆盖时间随机游走的树构建方法

• 发表时间: 2010
• 作者: 野中良哲;他
• 通讯作者: 他

An O(n log n)-Cover Time Random Walk on a Biconnected Graph

双连通图上的 O(n log n)-覆盖时间随机游走

• 发表时间: 2008
• 作者: Y. Hosaka;(H. Ono. K. Sadakane;M. Yamashita)
• 通讯作者: M. Yamashita)