=Paper=
{{Paper
|id=Vol-454/paper-5
|storemode=property
|title=A Method for Data Consistency Support in Mobile Ad hoc Distributed Systems
|pdfUrl=https://ceur-ws.org/Vol-454/paper5.pdf
|volume=Vol-454
}}
==A Method for Data Consistency Support in Mobile Ad hoc Distributed Systems==
https://ceur-ws.org/Vol-454/paper5.pdf
A Method for Data Consistency Support in Mobile Ad hoc
Distributed Systems♣
© Maxim Galkin
University of Saint-Petersburg
Universitetsky pr. 28, Peterhof, Saint-Petersburg, Russia
maksim.galkin@gmail.com
Abstract protocol can serve as a failover tool in such scenario.
The advantage of the proposed method is in its
This paper presents a research-in-progress indifference to an underlying data model. It demands all
report on a method for data consistency nodes to be aware of some initial data state (which can
support in ad-hoc mobile distributed systems, possibly be empty, it is only required as a common
based on the concept of high-level operations “starting point” for nodes operation history) and of a set
“compatibility” and operation history of high-level operations. After that is defined, the nodes
reconciliation. The proposed method also become autonomous and start applying those operations
utilizes tuple spaces as a communication model to their local replicas. At some points in time nodes
and accumulators as data structures for perform reconciliations of their replicas according to the
efficient conflict resolution. proposed protocol and through this achieve a consistent
and actual data. Due to the general approach this
1 Introduction method can be used to build a middleware platform for
consistency support in ad-hoc distributed systems.
In this paper we present a method for data consistency
support in an ad-hoc mobile distributed system. This
method combines some of the practices known for 2 Data Model and Operations
“nomadic” distributed systems with loose data For the sake of the proposed method, a set of defined
structures such as tuple spaces that can serve as a high-level operations over the data is more significant
medium hiding the intermittent mobile network than the data model itself and further in this paper we
connection. will only discuss operation set properties. At the same
Why do we consider methods for consistency time we must note that in some related works [1, 2]
support in ad-hoc distributed system at all? One of the special data model was crucial in defining such
advantages of such system is in the absence of a “single operations, which caused less conflicts and therefore
point of failure”. That is, all of the network nodes are were better suitable for collaborative work.
equally important, and if we keep their replicas In general, we can name two sides or two states of
consistent then our system can continue working even if the data in the system. One side is the real data, which
it loses most of the nodes. Of course, that also creates resides in the mobile agents, and which is continuously
more requirements for the reconciliation protocol, as we updated by them and another side is the ideal data, that
need to “handle” nodes, which were “offline” for a can be achieved by a full semantically-correct
period of time. reconciliation of all data replicas. In the process of work
Another advantage is the potentially unlimited our cloud of local data replicas strives to become closer
extensibility as there is no bottleneck like main server to the ideal state, where every agent knows the current
performance or main server connection bandwidth. A and actual state of data. Of course, in reality the degree
new node can join the network at any time, locate its of consistency depends on many factors, like the
“neighbors” and obtain the latest available data. connection quality between agents and the intensity of
Finally, in a mobile world it’s a possible scenario the continuous local updates.
that the known main servers are inaccessible, while the In most cases, a table of compatibility conditions is
“neighbor devices” can be still available. The proposed filled together with operations definition. We call two
operations “compatible” if none of them depends on
♣
Proceedings of the Spring Young Researcher's another. In the CoACT model [3] such conditions are
Colloquium On Database and Information Systems called “activity interleaving rules” and given in a form
SYRCoDIS, St.-Petersburg, Russia, 2009. of predicates for each pair of operations. In general,
This work is partially supported by Russian operations compatibility may depend on both their
Foundation for Basic Research under grant 07-07- nature (e.g., two “read” operations will never create a
00268. conflict) and data they are applied to.
To successfully maintain consistency the set of 4 The Proposed Protocol
operations for ad-hoc mobile distributed system must
ensure as few conflicts as possible, in other words We assume that numerous mobile nodes interact with
operations must be as compatible as possible, because each other by establishing connection with some of the
every conflict in such a system is a serious problem: other nodes in their “visibility range” and perform
two mobile nodes, which discover a data inconsistency reconciliation of their respective data replicas. During
during their interaction don’t possess any advantage the reconciliation nodes compare not the data itself, but
over each other, unlike it happens in “nomadic” the history of operations made over some initial data
distributed systems, where the fixed nodes have the state: a common “starting point”, which is known to all
priority, the most consistent state. Usually in ad-hoc nodes. If a conflict is discovered it is resolved according
distributed system it’s also impossible to draw a human to the rules for the given operations, one of the
operator into the process of conflict resolution, because conflicting operations has to be compensated and
the inconsistent state can be discovered at nodes that marked in history as rejected. This mark can make
aren’t the authors of the conflicting operations. future reconciliations faster.
Therefore every conflict resolution must be After the reconciliation we need to recalculate all
automatic in accordance with some pre-defined rules of the static data on the nodes that depend on the changed
consistency. Such rules can be of two major types: operations. If the changes have only affected such
differential (e.g. when the system takes one of two structures as accumulators [1] they don’t need the
conflicting operations basing on its timestamp) and recalculation.
integral (if the system, for example, has some pre- As a communication model between the mobile
defined objective function or cost function over the data nodes we can use the tuple spaces mechanism, such as,
model and it discards one of the conflicting operations for example, LIME [7] or JavaSpaces [8]. In this case
basing on the value of the function). nodes can create dynamic groups, sharing one tuple
space. In this tuple space a consistent set of operations
will be stored for each data element. If a new node
3 Transactional Properties of the System comes to the group, or a new operation is performed on
The above-stated implies that even if some operation a present node it triggers the reconciliation process as
has been committed at one of the nodes and lived in the described above. All nodes also synchronize their local
system for some period of time it is not guaranteed to be replicas with the common space to be ready to go
fixed in the system forever as one of the other nodes offline any time.
could have submitted a conflicting operation that will In this scenario the common tuple space can be
eventually overcome the first one. In other words, the found to correspond to a notion of a “cluster of
Durability property from the ACID set is not guaranteed consistency” [4], with the only difference that in our
by our system for the sake of Consistency. Here we can case no data in a cluster is durable. For example, if two
also notice that in ad-hoc distributed system no “global nodes from different clusters interact any of the
commit” or “strong” [4] operations are possible. On the operations in their replicas can be potentially conflicting
contrary, all operations in the system are “weak”, that is and subject for removal.
they are only applicable to the local replica of the data
and they are only guaranteed to be “safe” until next data 5 Conclusion
reconciliation with another node.
With respect to the other ACID properties such as We have introduced a method for consistency support
Atomicity and Isolation we should notice two levels of in a mobile ad-hoc distributed system, based on the
their applicability. If we consider our high-level reconciliation process of high-level operations histories.
operations as a specific form of transactions consisting We also presented a description of supported data
of some elementary read/write sub-operations, then models and the requirements for operations set. We
these transactions will satisfy both A and I properties. If have analyzed the transactional properties of the
on the other hand we introduce even higher-level proposed system and outlined a protocol for nodes
transactions that consist of our original operations we interaction.
will need to give away the highlighted properties, We plan to further develop this method with regards
similar to how it happens in the “sagas” transaction to an experimental proof of concept. We also plan to
model [5]. Otherwise, long-running isolated introduce metrics of the global consistency in such a
transactions will inevitably increase the number of mobile system to be able to evaluate the efficiency of
conflicts just like it is observed in other types of the method and/or compare our method with other
distributed database systems [6]. Such an increase in methods. Another way of applying such metrics is to
our system can lead to mobile nodes overload and use them in the described mobile system as an integral
overall decline in data quality, as compensative rule for operational histories reconciliation, thus we can
transactions can sometimes be ineffective in cleaning up sort out nodes, which have their replica so obsolete or
the database due to lack of transaction isolation. inconsistent that it doesn’t make sense to compare them
with the current data.
References
[1] A. Kozlova, D. Kochnev, B. Novikov. The
Middleware Support for Consistency in Distributed
Mobile Applications. Proc. of the Baltic
DB&IS'2004, 145-160, Riga, Latvia, Scientific
Papers University of Latvia, June 2004.
[2] O. Proskurnin, B. Novikov. Towards collaborative
video authoring. Proc. of ADBIS’03, 370-384,
Dresden, Germany, 2003.
[3] M. Rusinkiewicz, W. Klas, T. Tesch, J. Wasch, P.
Muth. Towards a Cooperative Transaction Model:
The Cooperative Activity Model. Proc. of the 21st
VLDB Conference, Zurich, Switzerland, 1995.
[4] E.Pitoura, B. Bhargava, O.Wolfson. Data
Consistency in Intermittently Connected
Distributed Systems. In Transactions on
Knowledge and Data Engineering, Nov 1999.
[5] H. Garcia-Molina, K. Salem. Sagas. ACM
SIGMOD Record, Volume 16, Issue 3, pp. 249-
259, 1987.
[6] J. N. Gray, P. Helland, P. O’Neil, D. Shasha. The
Dangers of Replication and a Solution. In
Conference on Management of Data, pp. 173-182,
Canada, June 1996.
[7] A. L. Murphy, G. P. Picco, G-C. Roman. LIME: A
Coordination Model and Middleware Supporting
Mobility of Hosts and Agents. ACM Transactions
on Software Engineering, Vol. X, No. X, pp. 1-48,
2006.
[8] E. Freeman, S. Hupfer, K. Arnold. JavaSpaces,
Principles, Patterns and Practice. Addison-Wesley,
1999.