Totally and causally ordered group messenger in Android
This is my second project in Android. It involves developing a group messenger that preserves total
ordering as well as causal ordering of all messages on the Android platform.
A sequence server is used to enforce total ordering across the system, and in a way which is different from the regular total ordering algorithm using a sequencer. Sequence server is a logical clock server whose only purpose is to serve sequence numbers.
A key observation made during the design was that the only case when the causal ordering breaks given that the system has been totally ordered is when – a peer sends two messages M1 and M2 in that order and M2 gets delivered before M1. In order to handle this, we only need to make sure that M2 gets a higher sequence number than M1 in a totally ordered algorithm. This is enforced in our algorithm because a message can only be multicast after it receives a sequence number, and therefore M1 is always guaranteed to have a lower sequence than M2. Having said that, a subtle point to be noted in implementation is – the message sending client will have to be synchronized if for any reason it has been implemented in a multi-threaded fashion.
Our algorithm works as follows:
Design Overview
- GroupMessenger (Multicast 2): The main activity class. On create, it launches a sequence server if it is running on the device with port 5554; then it launches the server thread. It also creates a client thread for sending each new message.
- SequenceServer: The sequence server is responsible for giving out universal sequence numbers.
- Client: The client thread is responsible for sending messages after ensuring the ordering algorithm is enforced. It uses a multicast service to send the message over the network.
- Server: The server thread is responsible for receiving messages from all the peers. It also responsible to enforce the algorithm by making sure that only messages in sequence are delivered and the rest are buffered.
- MulticastService (Multicast function): Multicasts the given message to a list of hosts by using a unicast service.
Totally and causally ordered algorithm
A sequence server is used to enforce total ordering across the system, and in a way which is different from the regular total ordering algorithm using a sequencer. Sequence server is a logical clock server whose only purpose is to serve sequence numbers.
A key observation made during the design was that the only case when the causal ordering breaks given that the system has been totally ordered is when – a peer sends two messages M1 and M2 in that order and M2 gets delivered before M1. In order to handle this, we only need to make sure that M2 gets a higher sequence number than M1 in a totally ordered algorithm. This is enforced in our algorithm because a message can only be multicast after it receives a sequence number, and therefore M1 is always guaranteed to have a lower sequence than M2. Having said that, a subtle point to be noted in implementation is – the message sending client will have to be synchronized if for any reason it has been implemented in a multi-threaded fashion.
Our algorithm works as follows:
- On initialization, the sequence server is launched with the initial sequence value of 0 (in our case, on the first emulator with port number 5554).
- When a peer has a message “m” to multicast, it unicasts a request (GET sequence_no) to the sequence server and waits for a reply.
- The Sequence Server unicasts a reply to the peer with the sequence number “seq_no”.
- Once the sequence number is obtained, the peer B-multicasts “<seq_no, m>” to group g
- On the receiving side, the peers store the received messages in a queue and check the value of sequence number “seq_no” of the received message with the expected sequence number “Seq_no”. If “Seq_no” == “seq_no”, the message is B-delivered.
Comments
Post a Comment