在分散式系統中，群組通訊是一個重要的通訊模式。而在群組通訊中，適當的訊息處理次序一直都是許多分散式應用一項基本的需求。順序號碼機制是很簡易、實用方式應用於完全次序的需求。 順序號碼機制主要有兩項考慮因素，亦即產生順序號碼時，沒有容錯機制設計。另一因素，針對重疊性群組系統中，排序者是整系統的瓶頸。本論文前首先針對此議題，提出有效率的機制，以達到提昇系統的效能。 針對排序者是整系統的瓶頸問題，我們導入簡單的多個協調排序者機制，運用於重疊性多群組中，以減輕單一排序者的負荷，我們採用每一群組一個排序者的方式，負責對送往各該群組的訊息做排序動作，其核心部分是仰賴一套非同步、又不需阻隔的協調方法，以低耗損的方式，進行相互重疊之群組排序者間的控制訊息交換，以完成一致的訊息處理順序安排。訊息處理次序是以一向量順序號碼表示之，任一成員根據此向量順序號碼，就可以很迅速的決定訊息的次序。此外，本論文也針對減少排序者間之控制訊息，提出三種改良方式，並將機制延伸至包含因果次序需求。
第二部針對行動分散式計算系統中，群組通訊中訊息次序的需求。由於無線通訊技術的蓬勃發展，許多具有行動性的計算器得以成為分散式系統的成員，參與系統中的合作計算，這也就形成了行動分散式計算系統。由於行動分散式計算系統與傳統分散式系統有其基本架構的不同，而且一般之行動處理機有硬體上的限制。其中，電池是其能量來源，由於電池有限的電力，行動處理機之傳輸必須考慮及此特性，以節約能源消耗，而無線通訊品質顯然也不如固定網路穩定，通訊可靠度是另一問題，而網路的頻寬又是其主要限制之一，當然，就系統邏輯而言，處理機的可移動性是其間最大的區別，由於處理機的移動，會造成訊息遺失，或在交換的過程中沒收到訊息的問題，令通訊工作變得困難。我們提出兩套有效率的訊息處理機制，以達到訊息次序的要求。首先我們利用位置固定的行動支援站之特性與功能，提出行動支援站傳播樹的概念，實現傳輸樹的觀念用於行動分散式計算系統中。我們採用行動支援站傳播樹的優點是群播訊息經由行動支援站傳播樹來傳遞，在此傳播樹中傳遞的群播訊息都是由行動支援站透過有線網路互相傳輸，不會耗用到無線網路的頻寬及行動處理機的資源，而且在傳播樹傳遞的群播訊息已經達到完全次序的需求，每個監督者只要負責轉送群播訊息給屬於該小群組的行動處理機，如此，行動處理機收到群播訊息就可以馬上處理而達到完全次序的需求。尤其是，我們提供了有效的同步以及移動換手機制，以協調在無線網路上的傳輸動作以及平順地整合由於處理機移動所產生的訊息傳輸工作的變動，在無線網路上因此得以免去不必要的訊息重複傳送行為。
第三部份我們在產生順序號碼容錯機制方面，提出一套不用集中排序者來產生順序號碼的方法解決完全次序需求，該方法主要是由系統中的行程來產生順序號碼，順序號碼資訊就儲存在所有行程中，不會因為任何一個行程的故障而無法再產生新的順序號碼，如此，在產生順序號碼就有容錯機制。
最後，針對無線應用網路環境，我們設計雙層機制以達到因果次序需求。該方法利用位置固定的行動支援站之特性與功能，實現行動支援站對於具多步繞線的行動處理機，進行區域管理機制，並應用ISIS CBCAST技術於各區域中行動處理機間，開發有效率的訊息傳輸暨處理演算法以減少附加的額外資訊，以達到區域間因果次序的要求。並且也應用ISIS CBCAST技術在各行動支援站透過有線網路互相傳輸訊息以達到行動支援站間因果次序。其中，如何正確的結合雙層ISIS CBCAST技術來達到整系統因果次序是本雙層機制的主要貢獻。另外，也提供了有效的同步以及移動換手機制，以平順地整合由於處理機移動所產生因果次序的變動。

In distributed computing systems, processes are often organized into groups for supporting various applications. Ordered delivery of messages in group communication has been an important issue. Sequence-number-based mechanisms have proven to be a simple, efficient, and practical approach to achieve total ordering delivery. There are two challenging issues that are faced in implementing sequence-number-based scheme for total ordering requirement. The first one is fixed sequencer method to generate the sequence number has poor fault tolerance as the sequencer may become a single point of failure. The other one is the sequencer site may become a bottleneck in terms of performance as all requests are addressed to the single site and the single sequencer does not scale to large group size or multiple groups. In this dissertation we first adopt a sequencer-based scheme to large group size or multiple groups. We introduce the concept of coordinating sequencers that arms to constructs a sequence array for a message to achieve the total ordering requirements for group communication systems with multiple overlapping groups. Our scheme assigns a sequence to each group. For a given message, the sequencer of the destination group constructs a sequence array by requesting for relative delivery positions from the sequencers of the overlapping groups. The sequence array is then used by any receiving process to determine the delivery sequence of the message. A salient feature of the protocol is that the coordination between the sequencers is performed in a simple, asynchronous and non-blocking manner. The delivery operation at a receiving process is very simple, and a message can be delivered as soon as it becomes deliverable.
Second, we address the messages ordering requirement in mobile computing system. There is a growing trend in developing applications for mobile computing systems in which mobile host computers retain their network connections while in transit. Mobile devices typically have severe constraints in terms of energy, computing and storage resources. Wireless channels used by mobile devices have significantly lower bandwidth than fixed communication links. Henceforth, it is important that group communication protocols designed for mobile computing environments keep the computing load and the communication overhead on mobile hosts low. Smooth host migration mechanism is also demanded for such protocols.
In this dissertation we propose an efficient adaptation of the propagation-tree technique to mobile computing systems with multiple overlapping groups. It takes advantages of the capabilities of stationary mobile support stations to overcome the deficiencies associated with mobile devices. We construct the propagation tree based on the stationary stations, rather than the mobile hosts. As a result, mobile hosts are relieved of the excessive load of forwarding messages and communications on wireless channels are confined to transmitting messages to destination processes. Moreover, the proposed protocol employs a mechanism to synchronize transmissions within a wireless cell. This serves to avoid redundant transmissions of a message in a wireless network in an attempt to achieve better utilization of the network bandwidth. Our mechanism relies on a handoff operation to deal with mobility of mobile devices. The handoff procedure ensures a smooth integration of a mobile host into a new cell, while preserving reliability of communication and total ordering of message delivery.
Next, we address a fault-tolerant scheme for generating global sequence numbers for total ordering requirement in group communication. Our solution is to maintain the information about the latest-used sequence number at multiple participant nodes for enhancing fault tolerance. In the protocol, each process may initiate the generation of sequence numbers independently for messages emitted by itself. No single process failure may crash the operation of the system.
Final, we also introduce a two-tier causal ordering protocol for wireless access network which support multihop wireless infrastructures. Our protocol is essentially an adaptation of ISIS CBCAST technique to mobile computing systems with multihop wireless infrastructures. The size of vector time on message is proportional to the number of mobile hosts in the zone. In addition, the delivery operation at a receiving mobile host is very simple, and a message can be delivered as soon as it becomes deliverable. These factors may amount to a significant saving of computing and communication overhead for mobile computing systems in which mobile devices are typically tight on resources. Furthermore, our mechanism relies on a handoff operation to deal with mobility of mobile devices. Cell switchings of mobile hosts do not trigger any message exchange in the wired network. The handoff procedure ensures a smooth integration of a mobile host into a new zone, while preserving the causal ordering property of message delivery.

[1] A. Abouaissa, A. Benlimance, and M. Maimi." A group communication model for distributed real-time causal delivery." Proceedings of the Seventh International Conference on
Computer Communication and Networks, pages 918--925, 1998.

[2] A. Acharya and B. R. Badrinath. "A framework for delivering multicast messages in networks with mobile hosts." Mobile Networks and Applications, 1(2), June 1996.

[3] S. Alagar and S. Venkatesan. "Causal ordering in distributed mobile systems. " IEEE Transaction Computers, 46(3):353--361, March 1997.

[4] L. Amanton and M. Naimi. "Total and causal ordering implementation in distributed computation ." Journal of Computing and Information, 2(1):301--321, 1996.

[5] Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, and P. Ciarfella. "Fast message ordering and membership using a logical token-passing ring." In International Conference on Distributed Computing Systems, pages 551--560, 1993.

[6] G. Anastasi and A. Bartoli. "On the structuring of reliable multicast protocols for mobile wireless computing." The Computer Journal, 46(2):146--160, 2003.

[7] G. Anastasi, A. Bartoli, and F. Spadoni. "Group multicast in distributed mobile systems with unreliable wireless network." In IEEE 18th proceeding on Reliable Distributed System, pages 14--23, 1999.

[8] V. Aravamudhan, K. Ratnam, and S. Rangarajan. "An efficient multicast protocol for pcs networks." In 2nd International Mobile Computing Conference, pages 25--34, March 1996.

[9] B. R. Badrinath, A. Acharya, and T. Imielinski. "Impact of mobility on distributed computations." Oper. Syst. Rev., 27(2):15--20, April 1993.

[10] R. Baldoni, C. Marchetti, and S. Tucci-Piergiovanni. "A fault-tolerant sequencer for timed asynchronous systems." In Proc. 8th International Conference Euro-Par, 2002.

[11] A. Bartoli. "Group-based multicast and dynamic membership in wireless networks with incomplete spatial coverage." ACM/Baltzer Mobile Networks and Applications, 3(2):175--188, June 1998.

[12] A. Bartoli and F. Spadoni. " A reliable multicast protocol for distributed mobile systems: Design and evaluation." IEEE Trans. on Parallel and Distributed Systems, 12(10):1009--1022, 2001.

[13] B. Bhargava, Yi Lu X. Wu, and W. Wang. "Integrating heterogeneous wireless technologies: A cellular aided mobile ad hoc network (cama)." Mobile Networks and Applications, 9(4):393--408, August 2004.

[14] K. P. Birman. "The process group approach to reliable distributed computing." Communications of the ACM, 36(12):37--53, 1993.

[15] K. P. Birman. "Building secure and reliable network applications." In WWCA, 1997.

[16] K. P. Birman and T. A. Joseph. "Reliable communication in the presence of failures." ACM Trans. on Computer Systems, 5(1):47--76, February 1987.

[17] K. P. Birman, A. Schiper, and P. Stephenson. "Lightweight causal and atomic group multicast." ACM Trans. on Computer Systems, 9(3):272--314, August 1991.

[18] J. M. Chang and N. F. Maxemchuck. "Reliable broadcast protocols." ACM Trans. on Computer systems, 2(3):251--273, August 1984.

[19] B. Charron-Bost, G. Tel, and F. Mattern. "Synchronous, asychronous, and causally ordered communication." Distributed Computing, 9(4):173--191, 96.

[20] S. Y. Cheung, M. H. Ammar, and M. Ahamad. "The grid protocol: A high performance scheme for maintaining replicated data." IEEE Trans. Knowledge and Data Eng., 4(6):582--592, December 1992.

[21] K.-H. Chi, L.-H. Yen, C.-C. Tseng, and T.-L. Huang." A causal multicast protocol for mobile distributed systems." IEICE Trans. Information and Systems, E83-D(12):2065--2074, January 2000.

[22] G.-M. Chiu and C.-M. Hsiao. "A note on total ordering multicast using propagation trees." IEEE Transaction Parallel and Distributed Systems, 9(2):217--223, 1998.

[23] G.-M Chiu and C.-M. Hsiao."Load-balanced generating sequence-numbers protocol for total ordering in overlapping groups." In The International Conference on Dependable Systems and Networks, Fast Abstracts, 2002.

[24] G.-M. Chiu and C.-M. Hsiao."Total ordering group communication protocol based on coordinating
sequencers for multiple overlapping groups." IEICE Transactions on Information and Systems, E87-D(8):2048--2057, 2004.

[25] G. V. Chockler, I. Keidar, and R. Vitenberg."Group communication specifications: a comprehensive study." ACM Computing Surveys (CSUR) , 33 (4):427--469, 2001.

[26] S. Corson and J. Macker."Mobile ad hoc networking (manet): Routing protocol performance issues
and evaluation considerations." IETF RFC 2501 , January 1999.

[27] G. Coulouris, J. Dollimore, and T. Kindberg. "Distributed Systems -- Concepts and Design." Addison-Wesley Ltd., 2001.

[28] F. Cristian, S. Mishra, and G. Alvarez. "High-performance asynchronous atomic broadcast."
Distributed System Engineering Journal, 4(2):109--128, June 1997.

[29] X.~D{\'e}fago, A.~Schiper, and P.~Urb{\'a}n. "Totally ordered broadcast and multicast algorithms: A comprehensive survey." Technical Report DSC/2000/036, \'{E}cole Polytechnique
F\'{e}d\'{e}rale de Lausanne, Switzerland, September 2000.

[30] P. D. Ezhilchelvan, R. A. Mac\^{e}do, and S. K. Shrivastava."Newtop: A fault-tolerant group communication protocol." In { International Conference on Distributed Computing Systems, pages 296--306, 1995.

[31] J. Fidge. "Timestamps in message-passing systems that preserve the partial ordering." In Proceedings of the 11 th Australian Computer Science Conference , volume 10, pages 55--66, February 1988.

[32] G. H. Forman and J. Zahorjan. "The challenges of mobile computing." IEEE Computer, 27(4):38--47, April 1994.

[33] T. Fujiwara, N. Iida, and T. Watanabe."An ad-hoc routing protocol in hybrid wireless networks for emergency communications.", In 24th International Conference on Distributed Computing Systems Workshops, pages 748--754, March 2004.

[34] H. Garcia-Molina and A. Spauster. "Ordered and reliable multicast communication.", ACM Trans. on Computer Systems, 9(3):242--271, August 1991.

[35] Z. Haas and S. Tabrizi. "On some challenges and design choices in ad-hoc communications." In Proceedings of IEEE MILCOM 98 Bedford Massachusetts, pages 187--192, October 1998.

[36] J. Ioannidis, D. Duchamp, and G. Q. Maquire."Ip-based protocols for mobile internetworking." In Proc. of ACM Symposium on Communication, Architectures and Protocols , pages 235--245, 1991.

[37] W. Jia, J. Cao, X. Jia, and C. H. Lee."Design and analysis of an efficient and reliable atomic mulitcast protocol." Computer Communications , pages 37--53, 1998.

[38] X. Jia. "A total ordering multicast protocol using propagation trees." IEEE Transaction Parallel and Distributed Systems , 6(6):617--627, June 1995.

[39] M. F. Kaashoek and A. S. Tanenbaum." Group communication in the amoeba distributed operating system." In International Conference on Distributed Computing Systems, pages 222--230, 1991.

[40] M. F. Kaashoek and A. S. Tanenbaum. An evalution of the amoeba group communication systems. In International Conference on Distributed Computing Systems, pages 436--447, May 1996.

[41] M.F. Kaashoek, A.S. Tanenbaum, and K. Verstoep. "Using group communication to implement a fault-tolerant directory service." In International Conference on Distributed Computing Systems , pages 130--139, 1993.

[42] T. Kindberg. "A sequencing service for group communication." In Tech. Report no. 698, Queen Mary \& Westfield College Dept. of CS, 1995.

[43] Y.-C. Kuo and S.-T. Huang."A geometric approach for constructing coteries and $k$-coteries." IEEE Transaction Parallel and Distributed Systems, 8(4):402--411, April 1997.

[44] L. Lamport. "Time, clocks, and the ordering of events in a distributed system." Communincation ACM, 21(7):558--565, July 1978.

[45] L. Liang, S. T. Chanson, and G. W. Neufeld."Process groups and group communications: Classifications and requirements." IEEE Transaction Computers, 23(2):56--66, February 1990.

[46] C.-M. Lin, G.-M. Chiu, and C.-H. Cho. "An efficient quorum-based scheme for managing replicated data in distributed systems." In Proc. Int. Conf. on Parallel Processing, pages 328--335, 1999.

[47] C.-M. Lin, G.-M. Chiu, and C.-H. Cho. "A new quorum-based scheme for managing replicated data in distributed systems." IEEE Transaction Computers, 51(12), 2002.

[48] W.D. List and N.H. Vaidya."A routing protocol for k-hop networks." In Wireless Communications and Networking Conference, IEEE WCNC., volume 4, pages 2545 -- 2550, 2004.

[49] W. S. Luk and T. T. Wong." Two new quorum based algorithms for distributed mutual exclusion."
In International Conference on Distributed Computing Systems , pages 100--106, 1997.

[50] F. Mattern, A. Schiper, and S. Toueg."The causal ordering abstraction and a simple way to implement it." In Information Processing Letters , volume 39, pages 343--350, 1991.

[51] M.J. Miller, W.D. List, and N.H. Vaidya. "A hybrid network implementation to extend infrastructure reach." In UIUC Technical Report , January 2003.

[52} S. Mishra, L. L. Peterson, and R. D. Schlichting."Consul: a communication substrate for fault-tolerant distributed programs." Distributed Systems Engineering , 1(2):87--103, 1993.

[53] A. Mostefaoui and M. Raynal."Causal multicasts in overlapping groups: towards a low cost approach." In International Conference on Distributed Computing Systems , pages 136--142, 1993.

[54] A. Nakamura and M. Takizawa.Causally ordering broadcast protocol. In International Conference on Distributed Computing Systems , pages 48--55, 1994.

[55] T. P. Ng. "Ordered broadcasts for large applications." In In Proc. 10th Symp. Reliable Distributed System , pages 188--197, 1991.

[56] A. Nilsson, J.J. Garcia-Luna-Aceves, and M. Sphon." Routing in hybrid ad hoc networks using service points." In IEEE 58th Vehicular Technology Conference, VTC 2003-Fall , volume 3, pages 2078--2082, October 2003.

[57] L. L. Peterson, N. C. Bucholz, and R.D. Schlichting. "Preserving and using contex information in interprocess communication." ACM Trans. on Computer Systems , 7(3):217--246, August 1989.

[58] R. Prakash, M. Raynal, and M. Singhal."An efficient causal ordering algorithm for mobile computing environments." In International Conference on Distributed Computing Systems , pages 744--751, 1996.

[59] R. Prakash and M. Singhal."Dependency sequences and hierarchical clocks: Efficient alternatives
to vector clocks for mobile computing systems." Wireless Networks, 3(12):349--360, 1997.

[60] S.-P. Shieh and F.-S. Ho. "A comment on 'a total ordering multicast protocol using propagation
trees" IEEE Transaction Parallel and Distributed Systems , 8(10):1084, October 1997.

[61] G. Singh and S. Badarpura. "Application ordering in group communication."In International Conference on Distributed Computing Systems Workshop , pages 11 -- 16, 2001.

[62] Joo-Han Song, Vincent W.S. Wong, and Victor C.M. Leung."Efficient on-demand routing for mobile ad hoc wireless access networks. IEEE Jounal On Selected Areas in Communications, 22(7):1374--1383, September 2004.

[63] A. S. Tanenbaum. Distributed Operating Systems.Prentice Hall, Inc., 1995.

[64] R. Vitenberg, I. Keidar, G. Chockler, and D. Dolev."Group communication specifications: a comprehensive study." ACM Computing Surveys (CSUR), 33(4):427--469, 2001.

[65] B. Whetten, T. Montgomery, and S. M. Kaplan."A high performance totally ordered multicast protocol." In Dagstuhl Seminar on Distributed Systems , pages 33--57, September 1994.

[66] Qi Xue and A. Ganz. "Adaptive routing in ubiquitous mobile access networks." In IEEE 58th Vehicular Technology Conference, VTC 2003-Fall, volume 5, pages 3070--3074, October 2003.

[67] X. Ye and J. A. Keane. "A multicast primitive for mobile hosts."In Proc. IEEE Conferece on Systems, Man and Cybernetcs , pages 1718--1723, 1996.

[68] L.-H. Yen, T.-L. Huang, and S.-Y. Hwang."A protocol for causal ordered message delivery in mobile computing system." ACM/Baltzer Mobile Networks and Applications, 2(4):365--372, 1997.