Bachelor Thesis
AtomChat
Popular messaging apps like WhatsApp, Signal, and Telegram do not guarantee total order of messages. Total order means that all participants receive the same messages in the same order. Without it, network delays and device synchronization issues can cause participants to see different versions of the same conversation. These apps do not enforce total order because it can negatively impact performance and scalability.
The table below shows a simple group chat example where lack of total order causes different participants to interpret the conversation differently:
| Intended Order | Alice’s View | Bob’s View | Charlie’s View |
|---|---|---|---|
| 1. Alice: Pizza or burgers? | 1. Alice: Pizza or burgers? | 1. Alice: Pizza or burgers? | 1. Alice: Pizza or burgers? |
| 2. Bob: Pizza! | 2. Bob: Pizza! | 2. Bob: Pizza! | 2. Charlie: Burgers for me. |
| 3. Charlie: Burgers for me. | 3. Charlie: Burgers for me. | 3. Alice: Pizza then! | 3. Alice: Pizza then! |
| 4. Alice: Pizza then! | 4. Alice: Pizza then! | 4. Charlie: Wait, I meant pizza too. | 4. Charlie: Wait, I meant pizza too. |
| 5. Charlie: Wait, I meant pizza too. | 5. Charlie: Wait, I meant pizza too. | 5. Charlie: Burgers for me. | 5. Bob: Pizza! |
Project Overview
In this project, we will develop a distributed messaging application that guarantees total ordering of messages. We will use a simple, leaderless, DAG-based protocol [1] to achieve this.
You will learn about
- Atomic broadcast protocols: a fundamental problem in distributed systems with applications in finance, cloud computing, and more.
- DAG-rider [1] : a foundational algorithm for atomic broadcast that has influenced many other protocols [2, 3, 4, 5, 6]
- Programming distributed systems in a peer-to-peer setting with libp2p [7], the library used by many of the world’s most important distributed systems
References
[2] Mysticeti: Reaching the Limits of Latency with Uncertified DAGs
[3] Bullshark: DAG BFT Protocols Made Practical
[4] Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus
[5] DAG it off: Latency Prefers No Common Coins
[6] DAG-based Consensus with Asymmetric Trust
[7] libp2p