An Efficient Causal Group Communication Protocol for Free Scale Peer-to-Peer Networks
Source abstract
Abstract
In peer-to-peer (P2P) overlay networks, a group of n (≥2) peer processes have to cooperate with each other. Each peer sends messages to every peer and receives messages from every peer in a group. In group communications, each message sent by a peer is required to be causally delivered to every peer. Most of the protocols designed to ensure causal message order are designed for networks with a plain architecture. These protocols can be adapted to use in free scale and hierarchical topologies; however, the amount of control information is O(n), where n is the number of peers in the system. Some protocols are designed for a free scale or hierarchical networks, but in general they force the whole system to accomplish the same order viewed by a super peer. In this paper, we present a protocol that is specifically designed to work with a free scale peer-to-peer network. By using the information about the network’s architecture and by representing message dependencies on a bit level, the proposed protocol ensures causal message ordering without enforcing super peers order. The designed protocol is simulated and compared with the Immediate Dependency Relation and the Dependency Sequences protocols to show its lower overhead.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Distributed systems and fault tolerance · Peer-to-Peer Network Technologies · Opportunistic and Delay-Tolerant Networks
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Laboratorio Nacional de Informática Avanzada (LANIA), Xalapa 91000, México
Computer Science Department, Instituto Nacional de Astrofísica, Óptica y Electrónica (INAOE), Puebla 72840, México
CONACYT—FIC, Universidad Michoacana de San Nicolás de Hidalgo (UMSNH), Morelia 58040, México
References (33)
Show source-provided references
1. Tarkoma, S. (2010). Overlay Networks: Toward Information Networking, Auerbach Publications.
2. Cohen, B. The BitTorrent Protocol Specification, Version 11031. Available online:http://www.bittorrent.org/beps/bep_0003.html.
3. Knutsson, B., Lu, H., Xu, W., and Hopkins, B. (2004, January 7–11). Peer-to-peer Support for Massively Multiplayer Games. Proceedings of the Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), Hong Kong, China.
4. Baset, S.A., and Schulzrinne, H.G. (2006, January 23–29). An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol. Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM 2006), Barcelona, Spain.10.1109/INFOCOM.2006.312 ↗
5. Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail10.1007/BF02277859 ↗
6. A Reliable Multicast Protocol for Distributed Mobile Systems: Designs and Evaluation10.1109/71.963414 ↗
7. Banik, S.M., Radhakrishnan, S., Zheng, T., and Sekharan, C.N. (2005, January 19–22). Distributed Floor Control Protocols for Computer Collaborative Applications on Overlay Networks. Proceedings of the International Conference on Collaborative Computing: Networking, Applications and Worksharing, San Jose, CA, USA.
8. Benzaid, C., and Badache, N. (2008, January 10–12). An Optimal Causal Broadcast Protocol in Mobile Dynamic Groups. Proceedings of the International Symposium on Parallel and Distributed Processing with Applications, Sydney, Australia.10.1109/ISPA.2008.36 ↗
9. Doulikun, D., Aikebaier, A., Enokido, T., and Takizawa, M. (2013, January 4–6). Experimentation of Group Communication Protocols. Proceedings of the 16th International Conference on Network-Based Information Systems (NBiS), Gwangju, Korea.10.1109/NBiS.2013.79 ↗
10. Friedman, R., and Manor, S. (2004). Causal Ordering in Deterministic Overlay Networks, Israel Institute of Technology.
11. Hsiao, C., and Liao, Y. (2011, January 21–23). Domain-Based Causal Ordering Group Communication in Wireless Hybrid Networks. Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication, Seoul, Korea.10.1145/1968613.1968764 ↗
12. Maddi, A., and Dahamni, F. (, 2001). An Efficient Algorithm for Causal Messages Ordering. Proceedings of the 2001 ACM Symposium on Applied Computing, Las Vegas, NV, USA.10.1145/372202.372438 ↗
13. Nishimura, T., Hayashibara, N., Enokido, T., and Takizawa, M. (2005, January 20–22). Causally Ordered Delivery with Global Clock in Hierarchical Group. Proceedings of 11th International Conference on Parallel and Distributed Systems, Fukuoka, Japan.
14. The Minimal Dependency Relation for Causal Event Ordering in Distributed Computing10.12785/amis/090108 ↗
15. Dependency Sequences and Hierarchical Clocks: Efficient Alternatives to Vector Clocks for Mobile Computing Systems10.1023/A:1019134007206 ↗
16. Taguchi, K., and Takizawa, M. (2002, January 17–20). Two-Layered Protocol for a Large-Scale Group of Processes. Proceedings of the Ninth International Conference on Parallel and Distributed Systems, Zhongli, Taiwan.
17. Tsuneizumi, I., Aikebaier, A., Enokido, T., and Takizawa, M. (2009, January 14–16). A Flexible Group Communication Protocol with Hybrid Clocks. Proceedings of the 7th International Conference on Advances in Mobile Computing and Multimedia, Kuala Lumpur, Malaysia.10.1145/1821748.1821838 ↗
18. Tsuneizumi, I., Aikebaier, A., Ikeda, M., Enokido, T., and Takizawa, M. (2010, January 4–6). A Scalable Hybrid Time Protocol for a Heterogeneous Group. Proceedings of the International Conference on Broadband, Wireless Computing, Communication and Applications, Fukuoka, Japan.10.1109/BWCCA.2010.73 ↗
19. Tsuneizumi, I., Aikebaier, A., Enokido, T., and Takizawa, M. (2010, January 20–23). A Scalable Peer-to-Peer Group Communication Protocol. Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications, Perth, WA, USA.10.1109/AINA.2010.116 ↗
20. Tsuneizumi, I., Aikebaier, A., Ikeda, M., Enokido, T., Takizawa, M., and Deen, S.M. (2010, January 14–16). Hybrid Clock-Based Synchronization in a Scalable Heterogeneous Group. Proceedings of the 13th International Conference on Network-Based Information Systems, Takayama, Japan.10.1109/NBiS.2010.88 ↗
21. Tsuneizumi, I., Aikebaier, A., Enokido, T., and Takizawa, M. (2010, January 15–18). Reduction of Messages Unnecessarily Ordered in Scalable Group Communication. Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems, Krakow, Poland.10.1109/CISIS.2010.119 ↗
22. Yen, L. (2000, January 12–14). Probabilistic Analysis of Causal Message Ordering. Proceedings of the Seventh International Conference on Real-Time Computing Systems and Applications, Cheju Island, Korea.
23. Zhou, S., Cai, W., Turner, S.J., Lee, B., and Wei, J. (2007). Critical Causal Order of Events in Distributed Virtual Environments. ACM Trans. Multimed. Comput. Commun. Appl., 3.10.1145/1236471.1236474 ↗
24. Necessary and Sufficient Conditions on Information for Causal Message Ordering and Their Optimal Implementation10.1007/s004460050044 ↗
25. Performance of the Optimal Causal Multicast Algorithm: A Statistical Analysis10.1109/TPDS.2004.1264784 ↗
26. An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments10.1006/jpdc.1996.1300 ↗
27. Chandra, P., and Kshemkalyani, A.D. (2004, January 4–8). Causal Multicast in Mobile Networks. Proceedings of the IEEE Computer Society’s 12th Annual International Symposium on Date of Conference:Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, Volendam, The Netherlands.
28. Yang, B., and Garcia-molina, H. (2003, January 5–8). Designing a Super-peer Network. Proceedings of the IEEE International Conference on Data Engineering, Bangalore, India.
29. Virtual Private Networking: An Overview. Available online: https://technet.microsoft.com/en-us/library/bb742566.aspx.
30. Time, Clocks, and the Ordering of Events in a Distributed System10.1145/359545.359563 ↗
31. OMNeT++ Discrete Event Simulator. Available online: https://omnetpp.org/.
32. Mattern, F. Virtual Time and Global States of Distributed Systems. Proceedings of Parallel and Distributed Algorithms;.
33. The causal ordering abstraction and a simple way to implement it10.1016/0020-0190(91)90008-6 ↗