跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 22:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:傅新豪
研究生(外文):Hsin -Hau Fu
論文名稱:以知識邏輯驗算兩個分散式計算問題的訊息複雜度下限
論文名稱(外文):A knowledge-based approach to verifying message complexity lower bounds of two distributed computing problems
指導教授:黃廷祿
指導教授(外文):Ting-Lu Huang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:62
中文關鍵詞:知識邏輯分散式計算
外文關鍵詞:knowledgedistributed computing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:166
  • 評分評分:
  • 下載下載:25
  • 收藏至我的研究室書目清單書目收藏:0
knowledge是一種modal logic,它是Halpern等人於1984年所提出,並且它提供一套統一的架構和工具方便吾人使用於不可解問題的證明,knowledge自此被當成分析的工具,廣泛地使用於分散式環境下不可解問題的證明。
本論文中,使用knowledge去驗算兩個分散式計算問題的訊息複雜度下限,驗算的問題是resynchronization problem以及infimum computation problem。Gerard Tel以組合數學方式證明任何可以解決這兩個問題的演算法都至少需要使用n-1個訊息,其中n是所有程序的總數。本論文中使用knowledge的架構驗算這兩個分散式計算問題的訊息複雜度下限,驗算結果顯示n-1的確都是這兩個問題的下限。本論文中的驗算再次顯示knowledge的確為一強大的分析工具。

Knowledge is a kind of modal logic. It was proposed by Halpern et al. in 1984, and provides a unified framework and a set of tools for formal proofs about impossibility results. Knowledge has been extensively used since then as an analytical tool to prove the impossibility result of the problem in distributed environments.
In this thesis, we use knowledge to verify message complexity lower bounds of two distributed computing problems. The problems are the resynchronization problem and the infimum computation problem. Gerard Tel provided two combinatorial proofs for these problems and showed that any algorithm that solves one of these problems needs at least n-1 messages, where n is the number of processes. We use knowledge’s framework to verify message complexity lower bounds of the two problems. The result of our verification shows that n-1 is indeed a lower bound of each problem. The result attests the common belief in the field of distributed computing that knowledge is really a powerful analytical tool.

摘要 I
ABSTRACT II
誌 謝 III
目錄 IV
第一章 簡介 1
1.1 概論 1
1.2 組織 2
第二章 PRELIMINARY Ⅰ:KNOWLEDGE邏輯系統 3
2.1 POSSIBLE WORLDS 3
2.2 KNOWLEDGE邏輯系統的LANGUAGE 3
2.2.1 邏輯系統的formula以及language 4
2.2.2 Knowledge邏輯系統的formula以及language 4
2.3 KNOWLEDGE邏輯系統中FORMULA的SEMANTICS 5
2.3.1 Kripke structure 5
2.3.2 formula的semantics 6
2.3.3 使用Kripke structure分析多行為人系統的實例 7
2.4 KNOWLEDGE的一些性質 8
2.4.1 Ki modal operator的S5性質 9
2.5 GROUP KNOWLEDGE 12
2.5.1 formula EGφ和CGφ的semantics 12
2.5.2 Common knowledge以及G-reachability 13
2.5.3 Induction Rule以及CGφ modal operator的S5性質 15
2.5.4 Knowledge hierarchy 18
第三章 PRELIMINARY Ⅱ:多行為人系統以及KNOWLEDGE 19
3.1 SYSTEM以及RUN 19
3.2 KNOWLEDGE以及分散式系統 22
3.2.1 Interpreted system 22
3.3 MESSAGE-PASSING SYSTEM 24
3.3.1 Reliable message-passing system 26
3.3.2 Synchronous message-passing system 26
3.3.3 Asynchronous message-passing system 27
3.4 COMMON KNOWLEDGE以及COORDINATED ATTACK PROBLEM 27
3.4.1 Coordinated attack problem 28
3.4.2 兩位將軍同時進攻的必要條件 28
3.4.3 Unbounded message delivery 32
3.4.4 Coordinated attack problem是無解的 34
第四章 驗算RESYNCHRONIZATION PROBLEM以及INFIMUM COMPUTATION PROBLEM的MESSAGE COMPLEXITY的LOWER BOUND 35
4.1 因果關係 35
4.2 PROCESS CHAIN 36
4.3 (P1,P2,…,PK)-REACHABILITY 37
4.4 A.M.P SYSTEM中KNOWLEDGE的增加以及減少 41
4.5 2個S5性質的延伸性質 43
4.6 驗算RESYNCHRONIZATION PROBLEM的MESSAGE COMPLEXITY的LOWER BOUND 46
4.7 驗算INFIMUM COMPUTATION PROBLEM的MESSAGE COMPLEXITY的LOWER BOUND 49
4.8 TEL的證明方法和KNOWLEDGE-BASED驗算方法的比較 53
第五章 結論 58
參考文獻 60
附錄 62

[AU 76] R. J. Aumann, Agreeing to disagree, Annals of Statistics 4(6), 1976, 1236-1239.
[CM 86] K. M. Chandy and J. Misra, How processes learn, Distributed Computing 1(1), 1986, 40-52.
[DM 90] C. Dwork and Y. Moses, Knowledge and common knowledge in a Byzantine environment: crash failures, Information and Computation 88(2), 1990, 156-186.
[FHMV 95] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi, Reasoning about knowledge, the MIT press, 1995.
[FIN 79] S. G. Finn, Resynch procedures and a fail-safe network protocol, IEEE Transactions on Communications 27(6), 1979, 840-845.
[GRA 78] J. Gray, Notes on database operating systems, In R. Bayer, R. M. Graham, and G. Seegmüller, editors, Operating Systems: An Advanced Course, volume 60 of Lecture Notes in Computer Science, chapter 3.F, page 465, Springer-Verlag, 1978.
[HOD 95] R. Hodel, An introduction to mathematical logic, PWS publishing company, 1995.
[HM 90] J. Y. Halpern and Y. Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM 37(3), 1990, 549-587.
[HZ 92] J. Y. Halpern and L. D. Zuck, A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols, Journal of the ACM 39(3), 1992, 449-478.
[KL 43] F. Klein-Barmen, Uber gewisse Halbverbände und kommutative Semigruppen, Teil I, Mathematische Zeitschrift 48, 1943, 275-288.
[LAM 78] L. Lamport, Time, clocks and ordering of events in a distributed system, Communications of the ACM 21(7), 1978, 558-565.
[LIU 98] C. L. Liu, Elements of discrete mathematics (2nd ed.), McGraw-Hill International, 1998.
[LL 59] C. I. Lewis and C. H. Langford, Symbolic logic (2nd ed.), New York: Dover, 1959.
[LYN 96] N. A. Lynch, Distributed algorithms, Morgan Kaufmann, 1996.
[MOO 85] R. C. Moore, A formal theory of knowledge and action, In Formal Theories of the Commonsense World, J. Hobbs and R. C. Moore, eds. Ablex Publishing Corp., Norwood, N. J., 1985, 319-358.
[MT 91] M. J. Merritt and G. Taubenfeld, Knowledge in shared memory systems, In Proc. 10th ACM Symp. on PODC, 1991, 189-200.
[TEL 91] G. Tel, Topics in distributed algorithms, Cambridge university press, 1991.
[TEL 00] G. Tel, Introduction to Distributed Algorithms (2nd ed.), Cambridge university press, 2000.
[YC 79] Y. Yemini and D. Cohen, Some issues in distributed processes communication, In Proc. of the 1st International Conf. on Distributed Computing Systems, IEEE, 1979, 199-203.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top