Application-Level Causally Ordered Broadcast for Large-Scale Group Communication

ChaYoung KIM  JinHo AHN  ChongSun HWANG  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.12   pp.2883-2889
Publication Date: 2005/12/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.12.2883
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Dependable Computing
group communication,  causal order delivery,  gossip,  scalability,  reliability,  

Full Text: PDF>>
Buy this Article

Gossip-based reliable broadcast protocols with reasonably weak reliability properties scale well to large groups and degrade system performance gracefully even if node failure or message loss rates increase compared with traditional protocols. However, although many distributed applications require highly steady performance only by allowing causality to be used asynchronously, there is no existing gossip-based protocol offering causally ordered delivery property more lightweight than totally ordered delivery one. This paper presents an application-level broadcast algorithm to guarantee causally-ordered delivery semantics based on peer to peer interaction models for scalability, reasonable reliability and stable throughput. Processes propagate each message with a vector time stamp much like the spread of rumor in society for a fixed number of rounds. Upon receipt of these messages, correct processes immediately deliver the corresponding messages to the application layers in a causal order. Simulation results show that the proposed algorithm outperforms the existing ones in terms of delivery throughput.