The implementation of these algorithms require your platform's atomic support. O(n) refers to the number of processes
Mutex protects a critical section from concurrent access. If you must guarantee entering the critical section eventually...
locks in a bounded time (i.e. realtime) of O(n)
for starvation-free binary mutual exclusion
for starvation-free n-ary mutual exclusion (with O(n) time and space)
Physical Clocks are hard (impossible?) to synchronize without errors. If you must know whether event s "causes" /
"happens before" event t...
relax constraints enough to agree on the order of causal events
compares iff event s "happens before" event t (with O(n) time and space)
checks if a clock has been seen by all other processes
GC by knowing if all processes have seen clock
- Causal Ordering
- Chandy & Lamport's Protocol (Consistent Global Snapshot)
- Causal Order Delivery
- Skeen's Algorithm (Total Order Broadcast)
- Distributed Consensus
- No node/link failure
- Skeen's Algorithm (Total Order Broadcast)
- Chang-Roberts Algorithm (Leader Election on Ring)
- Distributed Spanning Tree
- Crash Failure, Reliable Channel, Synchronous
- F + 1 Round Protocol
- No Failure, Unreliable Channel, Synchronous
- P(fail) = 1 / R Randomized Algorithm
- Crash Failure, Reliable Channel, Asynchronous (FLP Impossibility Theorem)
- Byzantine Failure, Reliable Channel, Synchronous
- N >= 4F + 1 Coordinator Protocol
- No node/link failure
- Self-Stabilizing
- Self-Stabilizing Spanning Tree
- Cuckoo Hashing
- Robin Hood Hashing
- Hopscotch Hashing
- Sliding Bloom Filter
- https://programming.guide/hash-tables.html
- Skeleton rendezvous hash