# Requirements for Proposals
* Archictural model: Client-Server model
* Dynamic discover
* Fault tolerance
* Voting
* Ordered reliable multicast
* Architecture diagram

# Proposal 1

Content
* Introduction
For our software project we have decided to develop a messenger application with distributed properties.

* Project requirements analysis
The application will follow the architectual model of server-client architecture. A server will advertise its avaiability to the network via broadcast.

A messenger client should be able to find servers via broadcast messages of the server. A messenger client will register and connect via TCP to a server. Connected to a server clients can find relevant messenging partners and be able to communicate with other clients. Messages sent over the server should be received by other clients via single or group chat using causal ordering with vector timestamps. In case of a missing message, e.g. detected through getting a message with a lot higher timestamp, the client sends a negative ACK to the server to receive the missing messages.
When a client sends a message to a server and the server detects the message having a older time stamp vector than the current time stamp vector, the client will reject the message and return a negative ACK to the sending client. The client will request the missing messages and update its own time stamp vector then resend the message.
The server always keeps track of the most recent time stamp vector and keeps a copy of all messages sent.

A client keeps listening to broadcast messages of servers. When the server its connected to, does no longer broadcast (due to e.g. crash), the client automatically tries to connect to a different server. The server this client connectes to then updates the mapping of all clients to servers and sends an update message to all other servers containng the changes that have been made. For this message a ACK message has to be returned from each server. A newly started server may also request a copy of the current mappings of clients to servers, from a server.

A server always takes care of set of clients. A client is always connected to one server at a time. Servers share registered client information between each other. Servers can pass on messages to other servers if recipient of a message is connected to a different server. Messages that at a given time can't be delivered to a client will be saved on the server until delivery. %TODO
In the case of multiple servers, the servers will vote on a leader that is then resposible for checking the availability of all servers, with a heartbeat. Internally a server will consist of multiple components with a component checking the availability of each component, also with a heartbeat. If a server leader is no longer available, a new leader will be vote by remaining servers.
For the sending of messages the application will follow the model of ordered reliable multicast. For this the server will generate message IDs for all messages sent by the clients to recipient and the client will implement two queue, handling incomming messages. The two queues are the hold-back queue to wait for missing messages and the delivery queue to send messages. The client will check the message IDs and compre them to received message ID. If the message directly follows the last received message, it gets delivered to application. If not, the message is stored in a hold-back queue until the previous message(s) have arrived.

Project:
* Messenger Application
* Client:
* sending messages
* receive messages
* find server
* register to server (requires sign-in information)
* request available chat partners from server
* saving messages/information (optinally)
* group chats + single chats
* list of contacts (potentially)
* list of all servers
* Server:
* collects client IDs
* register clients (TCP connection)
* save which server a client is connected to
* receives messages from clients and passes them on to the recipients
* every server holds a copy of that message
* contains a message history: <vector, message>
* advertise itself for discovery via broadcast
* registration of servers (taken care by leader)
* check if server components are still working (heart beat)
* saving of messages both sent and pending
* confirmation that a messsage was received (optionally)
* voting of leader for heart beat checking
* if leader becomes no longer available, a new leader is elected
* detection could be if a server does not receive a heartbeat ping in a certain time frame
* if old leader tries to check for heart beats it gets a special return message (-> "you're not the leader")
* voting on leader of servers: leader sends heart beat to servers
* internally server component sends heart beat requests to internal components
-> 2 levels of heart beats: server level
* message queue for messages to be sent (-> repeat sending until client confirms it receiving the message -> 2-way-handshake) -> use UDP for message transport
* question: how to not overload network, check if client is still there
* use case 2 servers:
* servers need to exchange client information such as available clients, message status, server the client is connected to
* server takes care of own connected clients and passes all messages on to another server which recipients are not taken care by this particular server
* all servers must contain a copy of a message
* messages:
* client sends a message to server
* server confirms message has been received (in case of timeout: client resends x times and if no response fails)
* server tries sending message to recipient
* single chat
* client compares message ID with last sent message ID
* group chat:
* casual ordering of messages with vetor timestamps
* ordered reliable multicast
* server writes message IDs (maybe clock plus message ID vector)
* note: client vector contains the number of each participants messages as an entry in the vector
* client checks and compares IDs to see if it has to wait for another message before delivering -> delivery queue and hold-back queue
* server takes care of ID consistency (see lecture slides on message vectors)
* if two messages are received with the same vector

# Proposal 2

## what information does the client have
- list received messages
- holdback queue for messages where messages missing inbetween
- vector clock for causal ordering of messages
- contact list
- server (decided at start up time or when connection is lost)

## what information/datenstructures does the server have
- Map<Client,Server>
- Holdback queue for Server messages (?)
- Map<Chat-Gruppe,List<Vector, Message>> -> message History
- Serverliste -> voting, who is leader
- leader
- Queue for sending out client messages
- pending messages (list)
## Processes:
### Client-server connections:
- (de-)registration: TCP
- sending a message to server: UDP -> expects an ACK msg (either negativ if Vector of client is outdated or positive if accepted)
- re-sends message periodically after time out (server has to send a msg to client when client msg has been delivered)

### Server-Client:
- message delivery: UDP, Multicast
- advertisement through broadcast

### Server-Server:
- Advertisement through broadcast
- message delivery: UDP, Multicast
- types:
- update server list (add, remove servers)
- update client-server mapping (which client belongs to which server)
- update message-vector list of group
- voting of leader
- heartbeat message
- inital message exchange (using TCP):
- request leader contact info
- registration at leader
- server list
- client-server mapping
- group informations <-- added
- message history
- leader <-- dont need becaus we requested to know who the leader is

----
## Dynamic discovery:
- servers advertise themselves via Broadcast
- clients can discover servers over those broadcasts and connect to them
- servers can find new group members through these broadcasts messages
- clients can find other clients through requesting a list of clients, currently conencted to any server in a server group.

## ordered reliable multicast:
For messages between clients we use causal ordered reliable multicast, because
- we can have multi groups which FIFO would not support
- for Total ordering we would need a global sequencer for the Message IDs which is diffcult if we use Servers as a gateway to have clients communicate with each other

## Voting:
### OLD:
- Build spanning tree with flooding algorithm
- For voting a spanning tree will be used to send out messages from the server that initiates the vote
- Three states: Not-voting (default), voting, finish-vote
- Not-voting(default):
- default state
- change to voting state when voting request message is received
- voting
- every server is casting their vote for a leader
- every server should collect the votes of children in spanning tree
- parent nodes collect votes from children and then pass on to their parent node when all are collected + their own vote
- change to "finish vote" when all votes have been collected
- finish vote
- new leader is selected and all other servers are informed by sending message results + new leader ID
- servers can confirm message
- if all servers confirm then all can change the state to "Not-voting" (default)
- server can reject if server e.g. server has information of another server ID not contained in message
- send negative response message
- receiving server goes abck to voting state
### NEW:
- Form ring with list of known servers (list is sorted each time a server gets added to the list)
- Hirschberg-Sinclair algorithm is used to elect leader
- all participants start a vote
- Election message contains the UUID (version 1 of UUID) of the sender, the current phase of the election process and a hop counter
- Reply messages contain the current phase and a participant UUID
- reason for using this is to reduce the amount of messages necessary in worst case scenario
- after registration: if no leader or more than 1 leader is present -> voting of new leader
- neuer Server -> hört auf broadcast ob schon server da sind (merkt sich vorhandene Server)
-> wenn ja, anfrage bei einen Server wer der Leader ist, register bei leader, und inital message exchange
-> wenn nein, start voting for leader

## Fault tollerance:
- Replication of data for fault tollerance:
- Server list
- leader ID
- Message History of Clients (group + single)
- Client-Server Mapping list
- Group chats (contain current group members + group ID) -> so the server knows which clients should receive message
- Mapping: <client, pending messages to be received>
- Case: server fails:
- servers:
- server fails heartbeat request and gets removed from server list by leader (alternatively over broadcast messages)
- all servers get an update to their server list
- client:
- searches new server to connect to. Client realises by not receiving any new broadcast messages from the server (->timeout)
- registers to new server

- Case: Client still active/available?:
- After registration Client needs send a message to the server every x mins/secs. Either through regular message sending (sending message to other client) or a ping to say the client is still active.

1. server receives message
2. checks the server-client mapping
3. if its the responsible server, check the time stamp of client
4. if client stamp is valid, send message to client
5. otherwise hold message
### Heartbeat:
- Leader checks for broadcast messages of each server
- leader pings servers (no broadcast message has been sent in x seconds) multiple times (maybe max. 3 with no reply) -> if no reply in timeframe -> EJECT

message format:
- Message Typ, Nachricht, timestamp/vectorclock (Json)

## Proposal Text:

For our clients to run smoothly, it must be possible to store several pieces of information. When the client is started or when the connection to the connected server is lost, it will connect to a server. This information must be stored because all further communication goes through this server. The client stores all received messages in lists to be able to display them in the different chats. In order to display the messages in the correct order, the vector clock of the message is checked when it is received. If it is determined that messages are missing, they are stored separately until the missing messages have been transmitted. The client also keeps a contact list to display them.
To ensure the functionality of the server, it must store several pieces of information. All servers in the system know which servers are available at all times. All servers in the system must know who is the currently designated leader, who must also be present in the known servers. The servers must also know the mapping of the client-server connections in order to send messages to the right places as quickly as possible. The servers have stored the information about group chats, which users are in this group, so that also a message can be stored for a message history in the groupchat. The messages received by the server but not yet forwarded to an online client are kept in the server until the client confirms the receipt of the message. If a client is no longer connected to any server, these messages are stored in a separeted list so that they can be transmitted as soon as the client reconnects to a server.
In the system there will be different processes to represent the different functions. These include the connection of a new client or server and the message transfer between client-server, server-client and server-server.
In the communication from client to server it is possible to register in the system. First servers are identified by receiving their broadcast messages. From this list of available servers then one is selected, in order to register with this, a TCP connection is opened. When the client terminates, it logs off from the server via a TCP connection. If the client sends messages to other clients, these messages are sent via UDP to the connected server. The server checks the message that it was sent by a registered client and also checks the vector clock that it matches to the previous messages. If the message is accepted by the server, it sends an ACK back to the client. If the message is rejected by the server, the server sends back an error message to the client. The client need to fix the problems with the message and resend the message. If the client does not receive a response from the server, the message is sent again after a certain time window until the server delivers a response to the client.
The communication between server and one or more clients takes place via UDP. Messages sent to clients are sent until an ACK is received from the client in response. If a message was delivered to a client, a message is sent to the sending client that the message was delivered. To identify itself as a server in the network, a broadcast, per UDP, is executed at defined intervals to indicate itself to clients and other servers.
To exchange information between servers that are already registered in the system, the messages are transmitted using the UDP protocol. Various information must be exchanged between servers via these messages:
- Servers are added to or removed from the known list of servers
- The mapping of client-server connections can be transmitted or changed
- the information which clients belong to a group chat can be changed
- Starting the voting of a new leader and the voting itself can be transmitted
- The Heartbeart messages are transferred

When a new server is started, it will request the contact information for the currently selected leader from an already broadcasting server. The new server then establishes a connection via TCP to the leader so that it can register. Afterwards all needed information will be transferred to the new server via this connection. This includes the already registered servers, the mapping of the client-server connections, the group chat information and the message history.

------------------
To achieve dynamic discovery of our servers, each server advertises itself on the network via broadcast messages. Clients listen for these messages and connect to the first server of which they receive a broadcast message. Other Serves also listen for these broadcasts messages to find an active group of servers to connect to or to form a new group of servers. Clients can discover other clients through requesting a list of all currently active clients from the server it is connected to.
For messages between clients (delivered by the servers) we use causal ordered reliable multicast, because we can have multi groups which FIFO would not support. For a total ordering of messages, we would need a global sequencer for the Message IDs, which is diffcult if we use multiple Servers as gateways to have clients communicate with each other.
To check if servers in the ring are still avilable, we select a leader among them to to periodically check if each server in the ring is still sending broadcast messages. If no new broadcast message has been received in x amount of seconds (exact timeframe to be determined), the leader pings the server. If then no respons eis received by the leader in x amount of seconds, the leader removes the server from the group und notifies every server in the ring with the changes to the server list.
The leader is the only member in the server ring, that can add and remove servers to/from the server ring.
A leader is elected via voting. For the election we use the Hirschberg-Sinclair algorithm.
In this algorithm all participants start a vote. Two different Message types are used, being election messages and reply messages. A Election message contains the ID of the sender, the current phase of the election process and a hop counter. To represent the ID of sender/server we use generated UUIDs comforming to version 1 of UUIDs in RFC 4122. A reply message contains the current phase of the election process and the participant (server) UUID. We chose to use this algorithm as it can be performed on ring structures. Also compared to the LaLann-Chang-Roberts algorithm this algorithm requires a lot less messages to be sent between members of the ring in the worst-case scenario.
All messages we send during this election process will be in JSON format, containing the above described content.
To make our programm more resillenct to failure we add some fault tollerance. For this we replicate a copy of several data structures to all servers part of the group/ring:
- Server list
- current leader ID
- Message History of Clients (both group and individual chats)
- Client-Server Mapping
- Group chats (contain current group members + group ID) -> so the server knows which clients should receive message
- List of messages to be delivered to individual clients that currently are not connected

The server list we need to effectively perform any voting that has to take place if the leader for example is no longer available/crashes. The current leader ID is necessary in case of a new server requesting ro join the group. In that case the server can redirect the requesting server to the leader of the group.
As Clients can request missing messages from the server it makes sense to store the messages sent to clients in the server. To avoid a single point of failure we replicate this data to all servers.
All servers also contain a mapping of clients to servers so the server knows if it needs to pass a message on to a server or if it can deliver the message to a client directly.
A server also keeps track of current participants in a group by mapping a chat ID to a list of chat group participants. This chat ID is also the key for the chat history. It would be possible to derive the list of participants through the vector clock we are using for the group chats. But then it would be difficult adding new chat members or to a group chat or group members leaving the group chat.
Finally a server will also be storing messages that currently can not be delivered to a client, due to a client becoming unavailable. These messages get stored and then delivered the next time a client connects to a server. As a client theoretically could connect to any server, a copy of this message list has to be stored on all servers to also avoid a single point of failure.

## Review:
add:
-vote new leader if a new sever joins

not understandable:
-Starting the voting of a new leader and the voting itself can be transmitted
-The Heartbeart messages are transferred

he didnt understand why we wrote:
For messages between clients (delivered by the servers) we use causal ordered reliable multicast, because we can have multi groups which FIFO would not support.

he sounded interested if we realy wanted to do Hirschberg-Sinclair algorithm. :D

message format:
- sender, target, Message Typ, Nachricht, timestamp/vectorclock (Json)