Efficient Barrier Synchronization on Wireless Computing Systems Nian-Feng Tzeng, Bhanurekha Kasula, and Hongyi Wu
Nian-Feng Tzeng, B. Kasula, Hongyi Wu · 2005
This work deals with efficient barrier synchronization for wireless cluster computing where nodes communicate with each other wirelessly in one or multiple hops. Such a computing system is referred to as a wireless computing system (WCS). Given t nodes participating in barrier synchronization on such a WCS of size n (/spl ges/ t), a backbone structure (BBS) is constructed and maintained to cover all the t participants throughout the course of barrier synchronization necessary for correct execution of an assigned task cooperatively. Two mechanisms for BBS construction, dubbed RAD/spl I.bar/Expansion and G/spl I.bar/Search, have been developed and evaluated empirically, and RAD/spl I.bar/Expansion is found to be more desirable. Our transport-layer barrier primitive is then implemented on the BBS constructed using RAD/spl I.bar/Expansion, with AODV as its underlying network protocol, for evaluation using NS-2. It arrives at faster barrier synchronization than a naive approach, which lets every participant send its check-in messages directly to the barrier controller. The barrier time gap widens as the number of participants increases under given mobility.