hengxin / distributed-mobile-memo

Distributed shared memory targeted at Android mobile phones.

Project distributed-mobile-memo

1. What is this project about?

This project aims to provide a distributed shared memory consisting of atomic registers over asynchronous message-passing networks. Both atomic, single-writer multi-reader (for short, SWMR) registers and atomic, multi-writer multi-reader (for short, MWMR) ones are supported. In the view of database, it can also be regarded as a distributed storage system which conforms to the atomic consistency.

In this project, such atomic registers reside on separate mobile phones.

2. How to use this project as a black box?

Suppose a distributed algorithm consisting of n processes that access (read/write) distributed shared atomic registers. To utilize this project, one follows the steps:

• To distinguish the processes, each process is assigned a unique identifier. This is often a requirement of the algorithm itself.
• All the participating processes are required to log into the project through the Login screen described below. It will ask for process identifier and ip address. Once logged in successfully, each process starts as a server replica which is also described below.
• Each register is associated with a unique key. Registers are accessed according to their keys.
• To determine whether the atomic registers accessed are of SWMR or MWMR types.
• For an atomic SWMR register with key k, each process plays as a client and
  • calls SWMRAtomicityRegisterClient.INSTANCE().put(k:Key, val:String) to write val to it;
  • calls SWMRAtomicityRegisterClient.INSTANCE().get(k:Key) to obtain its versioned value from which the value can be retrieved by calling VersionValue#getValue().
• For an atomic MWMR register with key k, each process plays as a client and
  • calls MWMRAtomicityRegisterClient.INSTANCE().put(k:Key, val:String) to write val to it.
  • calls MWMRAtomicityRegisterClient.INSTANCE().get(k:Key) to obtain its versioned value from which the value can be retrieved by calling VersionValue#getValue().

3. System models (See package sharedmemory)

3.1 Client/Server architecture

Each mobile phone holds a complete copy/replica of all data items and plays as a server. Clients issue their requests (read/write operations) to servers. All servers collectively process the requests and provide an illusion of a shared memory to the clients. In this project, the shared memory conforms to the atomic consistency.

Clients should implement the IRegisterClient interface to issue the get(key:Key) and put(key:Key, val:String) operations.

3.2 Data model (See package sharedmemory.data.kvs)

We use the simple key-value data model. Each server replica holds a collection of data items. Each data item is associated with a key, which is simply a string. Values are strings as well. To fit in most algorithms for emulating a distributed shared memory, each key-value pair is further associated with a version. Specifically, in the algorithm for emulating atomic registers in this project, a version is comprised of an integer process id (of a client, as described above) and an integer local seqno. For each key, all versions are totally ordered. To summarize, each server replica holds a collection of (key:Key, val:String, version:Version) triples.

KVStoreInMemory is an implementation of a database of key-value model. It maintains a HashMap of (Key, VersionValue) pairs, where Key is simply a String and VersionValue is a value associated with a Version. The class KVPair is a compressed representation of (Key, VersionValue) pairs.

3.3 Communication (See package sharedmemory.architecture.communication)

Clients and servers communicate by message-passing. Each message carries the ip of its sender, thus called IPMessage. The receivers (both the clients and the servers in this project) of messages implement the IReceiver interface to handle with received messages.

The core of the communication modular lies at the CommmunicationService class. It sends an IPMessage to a designated destination by calling public void sendOneWay(final String receiver_ip, final IPMessage msg). To start to listen to coming messages, a process (as a client or as a server) can call public void start2Listen(String server_ip). In addition, the CommunicationService class has implemented the onReceive() method of the IReceiver interface to propagate its received messages to AtomicityMessagingService. The latter class is related to the algorithm for emulating atomic registers and is described below.

4. Algorithm for emulating atomic registers (See package sharedmemory.atomicity)

4.1 Sketch of the ABD algorithm

4.2 Messages (See package sharedmemory.atomicity.message)

4.3

5. How to run the project?

distributed-mobile-memo's Issues

Socket programming for communication among clients and server replicas

The class MessagingServer is responsible for network communication among clients and server replicas. It does socket programming.

For now, it creates new Sockets for each message to send, which results in big performance issue.

To fix: create and store a (bidirectional) connection between each client and each server replica. All the messages involving a pair of client and server are sent via the single connection between them.

Experiment: introducing random message delivery delay to produce "old-new inversions"

Now there are many occurrences of concurrency patterns.
However, the "old-new inversions" are very very rare.

Old-new inversions is closely related to the order in which messages (for operations) are delivered at each replica node.

Therefore, I want to introduce random message delivery delay to produce more "old-new inversions".

Migrate to Java-8

At least, the synchronization on ConcurrentHashMap in KVStoreInMemory and AbstractAtomicityRegisterClient#Communication can be elegantly replaced.
See http://stackoverflow.com/a/24734868/1833118

Login screen

To join the system, an id (actually for clients only) and network connection are required.
In log-in screen, the user must provide an id and configure its network if needed.

Verifying atomicity and 2-atomicity: handling with the case of RESERVED_VALUE and "read from nowhere"

to handle with the case of RESERVED_VALUE and "read from nowhere".
Check the file: D:\GitHub\MobileMemo-Experiment\For ONI\replica factor = 3\async = 50\execution-0909-2312

Implementations of the IKVStore interface

IKVStore is an interface providing put(), get(), and remove() methods to access the data in store. IKVStore should be implemented in many different ways. For instance, in the side of a server replica, the key-value data may be stored in memory, in files, or in database. For a client, it may be a cache store.

WIFI Setting

provide UI for wifi setting

Refactor: file-system utility for file writing

Write an utility class for file-system supporting file writing

To implement SWMR by modifying MWWR

adding a cache to the single writer in SWMR;
reducing the first READ_PHASE of put() method

Simulate Poisson Distribution

How to simulate a Poisson distribution with a rate $\lambda$ (number per second)?

Integrate "SyncTime" into this app "mobile-memo"