進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2207201517505800
論文名稱(中文) 應用Proof-of-Assignment解決NP問題實現於霧運算平台
論文名稱(英文) Using Proof-of-Assignment to solve NP problem:A platform for Vapor Computing
校院名稱 成功大學
系所名稱(中) 資訊工程學系
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 103
學期 2
出版年 104
研究生(中文) 林詮量
研究生(英文) Quan-Liang Lin
學號 P76021166
學位類別 碩士
語文別 英文
論文頁數 48頁
口試委員 指導教授-鄭憲宗
口試委員-楊家輝
口試委員-陳煥
口試委員-林建良
口試委員-張惇育
中文關鍵字 霧運算  比特幣  工作量證明  NP問題 
英文關鍵字 Vapor computing  Bitcoin  Proof of Work  NP Problem 
學科別分類
中文摘要 有別於雲端運算平台,霧運算平台為使用者對使用者的對等服務網路,為分散式運算系統而不受中央系統所操控。
比特幣為當今最廣為人知的電子加密貨幣,不同於傳統的法幣由中央系統所監控,是透過比特幣參予者自治的分散式交易系統,比特幣經由稱為「挖礦」的過程所產生,透過交易系統的驗證合法性以及儲存紀錄來獲取生產的比特幣。
比特幣的挖礦為用戶付出一定的運算能力來解決特定運算工作量的工作量證明機制問題,藉以避免重複支付以及確認交易行為的合法性,然而,原有的工作量證明機制所運算出的結果僅是為了驗證有效性,而沒有實值上的意義,浪費參予者的運算資源。
本篇論文應用Proof-of-Assignment的機制,由比特幣工作量證明改良的演算法,結合基因演算法讓參予者在挖礦的過程中解決NP問題這種需要大量運算資源的問題,妥善有效的運用運算資源,並整合至比特幣的交易系統,同時結合圖形處理器平行運算的優勢加速運算,並實現在霧運算平台。
英文摘要 Unlike cloud computing platform, vapor computing platform is a peer to peer distributed computing network without centralized server.
Bitcoin is the most well-known crypto currency. Unlike traditional fiat money that monitored by centralized system, Bitcoin is a decentralized peer-to-peer system by participants that all the Bitcoin transaction are verify by peer-serving network. “Mining” is a process of generating Bitcoin through recording transactions and verifying the legality of payments.
Users have to offer their own computing power to confirm the legality of transactions in Bitcoin mining. Mining of bitcoin is to solve proof of work puzzles that users need to expend a certain amount of computational ability to verify payments and prevent double-spending problem. However, the results of original proof of work mechanism are meaningless value in waste of participants’ computing resources.
In this paper, we use proof of assignment algorithm, an enhanced proof of work algorithm, combined with genetic algorithms allow participation by solving NP problems in the process of mining that need a lot of computing resources, proper effective use of computing resources and integrated into Bitcoin system, combined with the advantages of graphics processors to accelerate parallel computing in the vapor computing platform.
論文目次 摘 要 I
Abstract II
ACKNOWLEDGEMENT III
TABLE OF CONTENTS IV
LIST OF TABLES VI
LIST OF FIGURES VII
Chapter 1. Introduction and Motivation 1
1.1. Introduction 1
1.2. Motivation 3
1.3. Overview 5
Chapter 2. Background and Related Work 6
2.1. Bitcoin 6
2.2. Crypto Currency with Scientific Purpose 7
2.3. Heterogeneous Computing 8
2.3.1. GPGPU 8
Chapter 3. System Design 11
3.1. Encoding NP problem to Genetic Algorithm 11
3.2. Proof-of-Work Model in Bitcoin 14
3.2.1. Proof-of-Work algorithm 14
3.2.2. Proof-of-Work Applied in Bitcoin 15
3.2.3. Proof-of-work Definition in Bitcoin 15
3.3. Proof-of-Assignment Model 18
3.4. Assignment Requirements 21
3.5. Map Stage 22
3.6. Reduce Stage 26
Chapter 4. Implementation and Experiment 29
4.1. Implementation 29
4.2. Experiment Setting 31
4.3. Experiment Results 33
4.3.1 Scalability 34
4.3.2 Performance 35
4.3.3 Stability 42
Chapter 5. Conclusion and Future Work 46
REFERENCES 47
參考文獻 [1] “BOINC”, https://boinc.berkeley.edu/, 2005.
[2] Satoshi Nakamoto, “Bitcoin: A peer-to-peer electronic cash system”, http://bitcoin.org/bitcoin.pdf, 2009.
[3] “Nvidia CUDA”, https://developer.nvidia.com/, 2008.
[4] Adam Back, “Hashcash – A Denial of Service Counter-Measure”, http://www.hashcash.org/papers/hashcash.pdf, 2002.
[5] “HSA”, http://www.hsafoundation.com/, 2012.
[6] “APU”, http://www.amd.com/, 2011.
[7] Jega Anish Dev, “Bitcoin mining acceleration and performance quantification”, Electrical and Computer Engineering (CCECE), 2014 IEEE 27th Canadian Conference on, pp. 1-6, 4-7 May 2014.
[8] “Litecoin”, https://litecoin.org/, 2011.
[9] Sunny King, “Primecoin: Cryptocurrency with Prime Number Proof-of-Work”, http://primecoin.io/bin/primecoin-paper.pdf, 2013.
[10] J. Holland, “Adaption in Natural and Artificial Systems”, Ann Arbor: The University of Michigan Press, 1975.
[11] Rattan Preet Singh, “Solving 0–1 Knapsack problem using Genetic Algorithms”, Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on, pp. 591-595, 27-29 May 2011.
[12] Feier, M.C., “Solving NP-Complete Problems on the CUDA Architecture using Genetic Algorithms”, Parallel and Distributed Computing (ISPDC), 2011 10th International Symposium on, pp. 278-281, 6-8 July 2011.
[13] Gerhard Reinelt, “TSPLIB—A Traveling Salesman Problem Library”, INFORMS Journal on Computing, pp. 376–384, 1995.
[14] “Bitcoin Source Github”, https://github.com/bitcoin/bitcoin, 2009.
[15] The Bitcoin Foundation, “Bitcoin.org”, https://bitcoin.org/en/, 2009.
[16] Yu-Chi Shen, “Proof of Assignment: An Economic Proof-of-Work Based Algorithm Performing Assignments in a Peer-Servicing Network,” Institute of Computer Science and Information Engineering, NCKU, 2014.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2020-08-24起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw