請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/93549完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳和麟 | zh_TW |
| dc.contributor.advisor | Ho-Lin Chen | en |
| dc.contributor.author | 吳政宏 | zh_TW |
| dc.contributor.author | Cheng-Hung Wu | en |
| dc.date.accessioned | 2024-08-05T16:30:52Z | - |
| dc.date.available | 2024-08-06 | - |
| dc.date.copyright | 2024-08-05 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-07-31 | - |
| dc.identifier.citation | [1] ALISTARH, D., ASPNES, J., EISENSTAT, D., GELASHVILI, R., AND RIVEST, R. L. Time- space trade-offs in population protocols. In Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (2017), SIAM, pp. 2560–2579.
[2] ALISTARH, D., ASPNES, J., AND GELASHVILI, R. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (2018), SIAM, pp. 2221–2239. [3] ALISTARH, D., AND GELASHVILI, R. Polylogarithmic-time leader election in popu- lation protocols. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II 42 (2015), Springer, pp. 479–491. [4] ALISTARH, D., GELASHVILI, R., AND VOJNOVIĆ, M. Fast and exact majority in pop- ulation protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (2015), pp. 47–56. [5] ANGLUIN, D., ASPNES, J., DIAMADI, Z., FISCHER, M. J., AND PERALTA, R. Com- putation in networks of passively mobile finite-state sensors. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (2004), pp. 290–299. [6] ANGLUIN, D., ASPNES, J., AND EISENSTAT, D. Fast computation by population proto- cols with a leader. Distributed Computing 21 (2008), 183–199. [7] ANGLUIN, D., ASPNES, J., FISCHER, M. J., AND JIANG, H. Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst. 3, 4 (dec 2008). [8] ASPNES, J., BEAUQUIER, J., BURMAN, J., AND SOHIER, D. Time and space optimal counting in population protocols. arXiv preprint arXiv:1611.07238 (2016). [9] BEAUQUIER, J., BLANCHARD, P., AND BURMAN, J. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In International Confer- ence on Principles of Distributed Systems (2013), Springer, pp. 38–52. [10] BEAUQUIER,J.,BURMAN,J.,CLAVIERE,S.,ANDSOHIER,D.Space-optimalcountingin population protocols. In International Symposium on Distributed Computing (2015), Springer, pp. 631–646. [11] BERENBRINK, P., GIAKKOUPIS, G., AND KLING, P. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (2020), pp. 119–129. [12] BURMAN, J., CHEN, H.-L., CHEN, H.-P., DOTY, D., NOWAK, T., SEVERSON, E., AND XU, C. Time-optimal self-stabilizing leader election in population protocols. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (2021), pp. 33–44. [13] CAI, S., IZUMI, T., AND WADA, K. How to prove impossibility under global fair- ness: On space complexity of self-stabilizing leader election on a population proto- col model. Theory of Computing Systems 50 (2012), 433–445. [14] CHEN, H.-L., DOTY, D., AND SOLOVEICHIK, D. Deterministic function computation with chemical reaction networks. Natural computing 13 (2014), 517–534. [15] CHEN,H.-P.,ANDCHEN,H.-L.Self-stabilizingleaderelection.InProceedingsofthe 2019 ACM Symposium on Principles of Distributed Computing (2019), pp. 53–59. [16] CHEN, H.-P., AND CHEN, H.-L. Self-stabilizing leader election in regular graphs. In Proceedings of the 39th Symposium on Principles of Distributed Computing (2020), pp. 210–217. [17] DIJKSTRA, E. W. Self-stabilizing systems in spite of distributed control. Communi- cations of the ACM 17, 11 (1974), 643–644. [18] DOTY, D., AND SOLOVEICHIK, D. Stable leader election in population protocols re- quires linear time. Distributed Computing 31, 4 (2018), 257–271. [19] FISCHER, M., AND JIANG, H. Self-stabilizing leader election in networks of finite- state anonymous agents. In Principles of Distributed Systems (Berlin, Heidelberg, 2006), M. M. A. A. Shvartsman, Ed., Springer Berlin Heidelberg, pp. 395–409. [20] IZUMI, T. On space and time complexity of loosely-stabilizing leader election. In In- ternational Colloquium on Structural Information and Communication Complexity (2015), Springer, pp. 299–312. [21] MITZENMACHER, M., AND UPFAL, E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. [22] SOLOVEICHIK, D., COOK, M., WINFREE, E., AND BRUCK, J. Computation with finite stochastic chemical reaction networks. natural computing 7 (2008), 615–633. [23] SUDO, Y., EGUCHI, R., IZUMI, T., AND MASUZAWA, T. Time-optimal loosely- stabilizing leader election in population protocols. arXiv preprint arXiv:2005.09944 (2020). [24] SUDO, Y., MASUZAWA, T., DATTA, A. K., AND LARMORE, L. L. The same speed timer in population protocols. In 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) (2016), IEEE, pp. 252–261. [25] SUDO, Y., NAKAMURA, J., YAMAUCHI, Y., OOSHITA, F., KAKUGAWA, H., AND MA- SUZAWA, T. Loosely-stabilizing leader election in a population protocol model. The- oretical Computer Science 444 (2012), 100–112. [26] SUDO, Y., OOSHITA, F., KAKUGAWA, H., AND MASUZAWA, T. Loosely-stabilizing leader election on arbitrary graphs in population protocols. In Principles of Dis- tributed Systems: 18th International Conference, OPODIS 2014, Cortina d'Am- pezzo, Italy, December 16-19, 2014. Proceedings 18 (2014), Springer, pp. 339–354. [27] SUDO,Y.,OOSHITA,F.,KAKUGAWA,H.,ANDMASUZAWA,T.Looselystabilizingleader election on arbitrary graphs in population protocols without identifiers or random numbers. IEICE TRANSACTIONS on Information and Systems 103, 3 (2020), 489– 499. [28] SUDO,Y.,OOSHITA,F.,KAKUGAWA,H.,MASUZAWA,T.,DATTA,A.K.,ANDLARMORE, L. L. Loosely-stabilizing leader election for arbitrary graphs in population protocol model. IEEE Transactions on Parallel and Distributed Systems 30, 6 (2018), 1359– 1373. [29] SUDO,Y.,OOSHITA,F.,KAKUGAWA,H.,MASUZAWA,T.,DATTA,A.K.,ANDLARMORE, L. L. Loosely-stabilizing leader election with polylogarithmic convergence time. Theoretical Computer Science 806 (2020), 617–631. [30] SUDO, Y., SHIBATA, M., NAKAMURA, J., KIM, Y., AND MASUZAWA, T. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems 32, 12 (2021), 3011–3023. [31] YOKOTA, D., SUDO, Y., AND MASUZAWA, T. Time-optimal self-stabilizing leader election on rings in population protocols. IEICE Transactions on Funda- mentals of Electronics, Communications and Computer Sciences E104.A, 12 (Dec. 2021), 1675–1684. [32] YOKOTA, D., SUDO, Y., OOSHITA, F., AND MASUZAWA, T. A near time-optimal pop- ulation protocol for self-stabilizing leader election on rings with a poly-logarithmic number of states. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2023), PODC ’23, Association for Computing Machinery, p. 2–12. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/93549 | - |
| dc.description.abstract | 在本文中，我們提出了一種能夠在有向環上解決自穩定領導者選舉問題的群 體協議。給定對群體規模 n 的知識 ψ = ⌈log log n⌉ + O(1)，該協議能夠以高機率 在步內選出唯一的領導者。此後，群體將永遠保持這個唯一的領導者。該協議使 用 polyloglog(n) 個狀態。與現有文獻相比，我們的協議保持了快速收斂速度，並 進一步減少了所使用的狀態數量。 | zh_TW |
| dc.description.abstract | In this paper, we propose a population protocol that solves self-stabilizing leader election on directed rings. Given a knowledge ψ = ⌈log log n⌉ + O(1) about the popu- lation size n, the protocol elects a unique leader within O(n2 log n log log n) steps with high probability. Thereafter, the population keeps the unique leader forever. The protocol uses polyloglog(n) states. Compared to the current literature, our protocol maintains a fast convergence speed and further reduces the number of states used. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-08-05T16:30:51Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-08-05T16:30:52Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements iii 摘要 v Abstract vii Contents ix List of Tables xi Chapter 1 Introduction 1 Chapter 2 Preliminary 7 Chapter 3 SSLE on Rings 11 3.1 Overview................................ 11 3.2 Cleaning ................................ 13 3.3 Creating Leaders ............................ 13 3.3.1 Generating Signals .......................... 17 3.3.2 Cleaning partial signals........................ 18 3.3.3 Signal Comparison .......................... 22 3.3.4 Signal Checking............................ 26 3.4 Suppressing............................... 29 3.5 EliminatingLeaders .......................... 30 3.6 Stabilizing ............................... 31 Chapter 4 Correctness and Convergence time 41 4.1 SafeConfigurations .......................... 41 4.1.1 Convergence ............................. 43 Chapter 5 Conclusion 57 References 59 Appendix A — CHERNOFF BOUNDS 65 | - |
| dc.language.iso | en | - |
| dc.subject | 群體協議 | zh_TW |
| dc.subject | 分散式系統 | zh_TW |
| dc.subject | 環 | zh_TW |
| dc.subject | 自我穩定 | zh_TW |
| dc.subject | 領導者選舉 | zh_TW |
| dc.subject | Leader Election | en |
| dc.subject | Self-stabilization | en |
| dc.subject | Rings | en |
| dc.subject | Population Protocols | en |
| dc.subject | Distributed System | en |
| dc.title | 環形的群體協議中，快速且空間高效的自我穩定領導者選舉 | zh_TW |
| dc.title | Fast and space-efficient self-stabilizing leader election in population protocols on rings | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 蔡孟宗;于天立;呂學一 | zh_TW |
| dc.contributor.oralexamcommittee | Meng-Tsung Tsai;Tian-Li Yu;Hsueh-I Lu | en |
| dc.subject.keyword | 分散式系統,群體協議,領導者選舉,自我穩定,環, | zh_TW |
| dc.subject.keyword | Distributed System,Population Protocols,Leader Election,Self-stabilization,Rings, | en |
| dc.relation.page | 65 | - |
| dc.identifier.doi | 10.6342/NTU202401577 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2024-08-02 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電機工程學系 | - |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-2.pdf | 4.96 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。