SOQ: A Service-Oriented Quorum-Based Protocol for Resilient Real-Time Communication in Partitionable Networks

We consider efficient real-time communication mechanisms for applications in unreliable and partitionable networks, where network partitions can occur unpredictably and nodes can join and leave arbitrarily. Utilizing quorum systems, we present a quorum-based protocol called SOQ to let nodes update and query service information to a selected set of servers (a quorum). Due to the intersection property of quorums, nodes can obtain latest updated information by simply accessing a quorum. To make the protocol adaptive to network partitions, we propose update/query triggering mechanisms to determine when nodes trigger updates/queries. A quorum access strategy for nodes to judiciously select a quorum to access is designed so that the probability that a query returns the latest service information is maximized. We give in-depth analysis of the protocol, including the communication overhead, load and availability relationship of quorum systems and timeliness analysis of distributed applications. Our experimental studies show that SOQ is resilient to network partitions without incurring large communication overhead. By carefully choosing the size of the quorum system, the distributed application can be executed more quickly and the load of quorum system can be reduced. I