Inconsistency Detection Framework

Navigation: [ Introduction | System Overview | Publications | People | Progress ]

Introduction

Background

Conventionally, consistency control protocols, such as strong consistency protocols or optimistic consistency protocols that increase the availability while tolerate relaxed inconsistency among nodes, are predefined and deployed before the system starts to run an application. We refer to this scheme as inconsistency avoidance .

While inconsistency avoidance can be effective in a small-scale networked system, such as a small cluster, it has some drawbacks in an Internet-scale environment, such as Grid. In this environment, a strong consistency protocol can be very costly to maintain because of the membership maintenance and strict protocol enforcement cost.

On the other hand, optimistic consistency protocol relieves the costly maintenance and strict enforcement burden associated with strong consistency protocols; however, it also does not suit the large-scale distributed system because it is predefined. In an environment where many applications are deployed, providing a predefined consistency protocol can be either overkill when an application does not need that strong consistency, or insufficient when an application needs stronger ones.

IDF (Inconsistency Detection Framework)

Thus, we propose a framework to detect inconsistency in a timely manner when it occurs instead of avoiding it in the first place. We refer this as inconsistency detection.

IDF's primary advantages are:

• First, it removes the costly membership management requirement that is used to enforce a consistency in the first place. Instead, it detects the inconsistency when it happens. That makes the system scalable. Besides, by ensuring that the potential inconsistent behavior be detected in a timely manner, a system can combine the results (if the results are combinable), break the tie or alert the users so that they can resolve the conflict as soon as possible using appropriate resolution protocols.
• Second, after the inconsistency is detected, the system can respond based on the application semantics. That is, it resolves the inconsistency when it is needed, while letting the detected inconsistency continue to exist when it is tolerable or even preferred.

System Overview

As an alternative to inconsistency avoidance, the inconsistency detection framework detects inconsistency among nodes in a timely manner. A logical diagram of this framework is shown in the figure below. In this framework, multiple applications share data and services through the support of the Internet-scale middleware and the inconsistencies among them are detected by the detector. Upon detection, the detector consults with the inconsistency level monitor (step 1 and step 2) before reaction is initiated. Based on the applications' semantics, if the inconsistency is tolerable, the detector does not react; otherwise, the detector informs the inconsistency resolution model to resolve this inconsistency (step 3).

Publications

• Yijun Lu, Ying Lu, and Hong Jiang, Adaptive Consistency Guarantees for Large-Scale Replicated Services, In Proc. of the 2008 IEEE International Conference on Networking, Architecture and Storage (NAS 2008), Chongqing, China, June 12-14, 2008. pp. 89-96.
• Yijun Lu, Xueming Li, and Hong Jiang, Accurate Performance Modeling and Guidance to the Adoption of an Inconsistency Detection Framework, In Proc. of the 2008 IEEE International Conference on Networking, Architecture and Storage (NAS 2008), Chongqing, China, June 12-14, 2008. pp. 193-200.
• Yijun Lu, Ying Lu, and Hong Jiang, IDEA: An Infrastructure for Detection-based Adaptive Consistency Control in Replicated Services, In Proc. of the 16th International Symposium on High Performance Distributed Computing (HPDC-16), Monterey, CA, June 27-29, 2007. ACM Press, pp. 223-224. (Extended Abstract) [Presentation]
• Yijun Lu, Ying Lu, and Hong Jiang, IDEA: An Infrastructure for Detection-based Adaptive Consistency Control in Replicated Services, Technical Report TR-UNL-CSE-2007-0001, University of Nebraska-Lincoln, January 2007.
• Yijun Lu, Xueming Li, and Hong Jiang, IDF: an Inconsistency Detection Framework – Performance Modeling and Guide to Its Design, Technical Report TR-UNL-CSE-2006-0003, University of Nebraska-Lincoln, March 2006.
• Yijun Lu, Hong Jiang, and Dan Feng, An Efficient, Low-Cost Inconsistency Detection Framework for Data and Service Sharing in an Internet-Scale System, In Proc. of IEEE International Conference on e-Business Engineering (ICEBE 2005), Beijing, China, Oct. 18-20, 2005. pp.373-380. [Talk slides]
• Yijun Lu and Hong Jiang, A Framework for Efficient Inconsistency Detection in a Grid and Internet-Scale Distributed Environment, In Proc. of the 14th IEEE International Symposium on High Performance Distributed Computing (HPDC-14), Research Triangle Park, NC, July 24-27, 2005. pp.318-319. (Extended Abstract) [Presentation]

People

Progress

We are currently investigating its implication to different applications.