臺灣博碩士論文加值系統

分散式資源分配在分散式系統 (Distributed System) 中是很重要的問題，可使系統資源 (Resources) 在互斥 (Mutual Exclusion) 情況下，依序被行程 (Processors) 所使用。
本文提出以不受涵蓋法團結構 (Nondominated Coterie)，來解決分散式資源分配 (Distributed Resource Allocation) 的問題。不受涵蓋法團結構比受涵蓋法團結構擁有較高可使用性 (Availability)。本篇所提方法，使用不受涵蓋法團結構，當兩個以上不受涵蓋法團結構相互聯集與結合之後，形成之新法團結構對原來法團結構而言，亦會是不受涵蓋的。
於第一章緒論裡，首先介紹在分散式系統中，法團結構常被用來有效率解決互斥性問題，亦可用來解決分散式資源分配的問題。
第二章對於基礎觀念做一些概略性介紹：何謂分散式資源分配、法團結構、局部法團結構。局部法團結構 (Local Coterie) 是法團結構的延伸，在局部法團結構中，由於行程間使用之資源可能不同，因此每個行程都只與和它使用相同資源之行程有關，當它得到所有所需資源後，即可進入臨界區間。假設行程皆在有限時間內完成工作，並釋放所使用資源。
第三章中將分別介紹在分散式系統與分散式資源分配下，如何辨識一個法團結構是否具有不受涵蓋之特性，以及在分散式資源分配下，利用不受涵蓋法團結構相互聯集與結合之後，產生的新法團結構對於原來法團結構保有不受涵蓋的特性，此外，同時也將介紹聯集與結合之方式與證明保有不受涵蓋的特性。
第四章主要是對於定理做一個延伸與證明其正確性，在分散式資源分配下，如何建構不受涵蓋法團結構之方式。不論聯集前法團結構個數多少，只要聯集前每個法團結構皆具有不受涵蓋之特性，則聯集後之新法團結構，對於原來法團結構仍保有不受涵蓋之特性。
最後第五章我們做一個總結，本文提出在分散式資源分配下，藉由不受涵蓋法團結構之聯集，產生新法團結構對於原來法團結構仍保有不受涵蓋之特性。由於不受涵蓋法團結構比受涵蓋法團結構擁有較高可使用率與容錯性，因此使用不受涵蓋法團結構將有效率解決分散式資源分配的問題。對於因行程毀壞或網路鏈結發生失誤，所造成錯誤亦有較高的容錯性。

The resource allocation problem is a fundamental problem in distributed systems. In this paper, we focus on constructing nondominated (ND) coteries to solve the problem. Distributed algorithms using coteries usually incur lower communication overhead and have higher degree of fault-tolerance, and ND coteries are candidates for achieving the lowest communication cost and the highest degree of fault-tolerance.
We use an operation called pairwise-union (p-union), which can be applied to known coteries to generate coteries for solving the resource allocation problem. We develop a theorem to check whether a coterie used for resource allocation is dominated or not. By the theorem, we prove that the p-union operation can be applied to ND coteries to generate new ND coteries for resource allocation.

Chapter 1 Introduction
Chapter 2 Preliminaries
2.1. Distributed Resource Allocation
2.2. Coterie
2.3. Local coteries
Chapter 3 Theorem for Nondominated Coteries
Chapter 4 Extension and Correctness
Chapter 5 Conclusion

References
[AE91] D. Agrawala and A. El Abbadi, “An efficient and fault-tolerant solution for distributed mutual exclusion,” ACM Trans. Comp. Syst., 9(1):1-20, 1991.
[AJ92] G. Agrawal and P. Jalote, “An efficient protocol for voting in distributed systems,” in Proc. of the 12th IEEE International Conference on Distributed Computing Systems, pp. 640-647, 1992.
[BP92] J. Bar-Ilan and D. Peleg, “Distributed Resource Allocation Algorithms,” Lecture Notes in Computer Science 647(WDAG ¢92), pp. 276-291, 1992.
[CM84] K. M. Chandy and J. Misra, “The drinking philosophers problem,” ACM Transactions on Programming Languages and Systems, 6(4):632-646, 1984.
[CS95] M. Choy and A. K. Singh, “Efficient Fault-Tolerant Algorithms for Distributed Resource Allocation,” ACM Transactions on Programming Languages and Systems, 17(3):535-559, 1995.
[CWH01] Z. Cheng and Y. Wada and S. Hashimoto and A. He and T. Huang, “A New Method for Constructing Efficient Local Coteries,” in Proc. of 15th International Conference on Information Networking, pp. 512 —517, 2001.
[Dij65] E. W. Dijkstra, “Solution to a problem in concurrent programming control,” CACM, 8(9):569, 1965.
[Dij71] E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, 1:115-138, 1971.
[FLBB79] M. Fisher, N. Lynch, J. Burns, and A. Borondin, “Resource allocation with immunity to limited process failure,” in Proc. of 20th IEEE annual symposium on foundations of Computer Science, pp. 234—254, 1979.
[GB85] H. Garcia-Molina and D. Barbara, “How to assign votes in a distributed system,” JACM., 32(4):841-860, 1985.
[HJK93] S.-T. Huang, J.-R. Jiang and Y.-C. Kuo, “k-Coteries for fault-tolerant k entries to a critical section,” in Proc. of the 13th IEEE International Conference on Distributed Computing Systems, pp.74-81, 1993.
[JH94] J.-R. Jiang, S.-T. Huang, “Obtaining Nondominated k-Coteries for Fault-Tolerant Distributed k-Mutual Exclusion,” in Proc. IEEE Int¢l Conf. Parallel and Distributed Systems, pp. 582—587, 1994.
[JHK97] J.-R. Jiang, S.-T. Huang, and Y.-C. Kuo, “Cohorts structures for fault-tolerant k entries to a critical section,” IEEE Trans. on Computers, 48(2):222-228 , 1997.
[Jia02] J.-R. Jiang, “Distributed h-out of-k Mutual Exclusion using k-Coteries,” Manuscript, 2002.
[Jia95] J.-R. Jiang, “Fault-tolerant distributed mutual exclusion with O(1) message overhead,” in Proc. of the 13th International Conference on Applied Informatics, pp.228-231, 1995.
[KFYA94] H. Kakugawa, S. Fujita, M. Yamashita, and T. Ae, “A distributed k-mutual exclusion algorithm using k-coterie,” Information Processing Letters, 49:213-238, 1994.
[KH98] Y.-C. Kuo and S.-T. Huang, “Recognizing Nondominated Coteries and wr-Coteries by Availability,” IEEE Trans. on Para. and Dist. Sys., 9(8):721-728, 1998.
[Kum91] A. Kumar, “Hierarchical quorum consensus: A new algorithm for managing replicated data,” IEEE Trans. Comp., 40(9):996-1004, 1991.
[KY96] H. Kakugawa and M. Yamashita, “Local coteries and a distributed resource allocation algorithm,” Transactions of Information Processing Society of Japan, 37(8):1487-1496, 1996.
[Lam78] L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” CACM, 21(7):558-565, 1978.
[Nei93] M. L. Neilsen, “Measures of importance and symmetry in distributed systems,” in 5th IEEE Symposium on Parallel and Distributed Computing, Dallas, TX, Dec. 1993.
[NM94] M. L. Neilsen and M. Mizuno, “Nondominated k-coteries for multiple mutual exclusion,” Inform. Porcess. Lett., 50:247-252, 1994.
[Ray91] M. Raynal, “A distributed solution for the k-out of-m resources allocation problem,” Lecture Notes in Computer Sciences, Springer Verlag, 497:599-609, 1991.
[Rhe95] I. Rhee, “A fast distributed modular algorithm for resource allocation,” in Proc. of the 15th International Conf. on Dist. Comp. Sys., pp. 161-168, 1995.
[Tho79] R. H. Thomas, “A majority consensus approach to concurrency control,” ACM Trans. Database Syst., 4(2):180-209, 1979.