Opportunistic network applications are usually assumed to work only with unordered immutable messages, like photos, videos or music files, while applications that depend on ordered or mutable messages, like chat or shared contents editing applications, are ignored. In this chapter, we examine how causal and total ordering can be achieved in an opportunistic network. By leveraging on existing dissemination algorithms, we investigate if causal order can be efficiently achieved in terms of hit rate and latency compared to not using any order. Afterwards, we propose a Commutative Replicated Data Type algorithm based on Logoot that uses the nature of opportunistic networks to its advantage. Finally, we present the results of the experiments for the new algorithm by using an opportunistic network emulator, mobility traces and chat traces.
TopI. Introduction
In the recent years, Opportunistic Networks (ONs) have become an important research field as a viable solution for mobile networks. ONs use the store-carry-and-forward (SCF) paradigm to facilitate communication between mobile devices as smartphones or laptops, even if these devices might never be directly accessible (Pelusi, Passarela, & Conti, 2006). Nodes can join and leave the network at any time, the content creators and the nodes interested in the data might never have a direct contact or they not might even be aware of each other existence. A node is aware only of those that come in direct contact with it. Due to these reasons, there is no central entity that knows about the network topology and how each node is connected to each other.
Most of the work in ONs has been directed towards achieving message forwarding or dissemination, where messages are usually considered immutable. Only a few researchers have tackled the problem of mutable content that requires a given order, even though these represent important user applications. Consider the case of discussion forums, where user post news or questions in discussion threads, and other users can respond to them. While different discussion threads are independent from each other and do not require any order, messages in the same thread should respect a total order, so that every user sees the same discussion.
Similarly to discussion forums, we have social networks, where users post something about themselves, or an interesting article, melody or citation they have found on the internet or somewhere else, which also requires a total order for future responses. Other types of applications that require a total order are collaborative editing applications, like Google Docs (Google, 2015b) or wiki pages. Every participant in a collaborative editor, or even a simple viewer of a wiki page, should have a consistent view of the contents. It is not permitted to have strings placed in different orders at different users (e.g. “This is a wiki page” at user1 vs. “This a page wiki is” at user2 – the misalignment here being result of users seeing text change updates in wrong order), as future updates will not correctly propagate to other nodes.
Though we have explained the importance of total ordering for applications with mutable contents, one might ask why these applications should even be supported in an ON environment, when they already exist in traditional environments. Though there are multiple reasons, we refer the reader to the recent example of FireChat, the chat application being used during the Hong Kong’s protests to broadcast on mesh networks the revolution live between participants (Open Garden, 2015)(Fitzpatrick, 2014) (Daileda, 2014). The application requires only an ON environment to work, without any need to run over a traditional network infrastructure. Still, on such an infrastructure, if becomes more important to show an order or a relation between distributed messages being exchanged.
A first reason to support such kind of applications is mobility, a base element of ONs. In recent years, users have shifted from desktops to laptops and smartphones, and more recently even to wearables as smartwatches. An ON infrastructure should support, in fact, as many types of applications as possible. Another reason is that regions in emerging countries (i.e. India or countries in Africa) are not properly connected to the global network, but, as smartphones have become affordable through programs as Android One (Google, 2015b), ONs represent a viable solution for connecting these devices, solution that will lead to a request of all types of applications similar to the ones mentioned above. Lastly, but not lastly, an important reason is privacy. ONs are able to work without connecting to the global network, providing an isolated environment. If participant nodes in ONs are not allowed to read the contents of the messages they carry unless they are the destination, government agencies or hackers will not be able to easily eavesdrop, as messages are exchanged only between the nodes themselves, without the help of an infrastructure that can route messages wherever it wants.