## Consistency models

1. In the "Conclusion" part of the paper "Shao@SIAM J. Comput.'11":
 - complexity separation between consistency conditions, i.e., proves some lower bound on the cost of any algorithm for some consistency condition
 - identify certain problems that cannot be solved at all under some consistency conditions
 - multi-writer safe registers are not yet well defined
 - formalizing the multi-writer version of consistency conditions met by the probabilistic quorum systems
 - semantics and consistency models of other data structures, which are built on top of quorum systems
 
2. Simulations of shared registers without "real-time" semantics:
  - causal consistency $\Rightarrow$ sequential consistency

3. Probabilistic quorum systems for multi-writer atomic registers
  - definition
  - probabilistic analysis
  - refer to [Item 1] and the paper "Randomized registers and iterative algorithms"

4. Wait-free **mutual exclusion** based on causal/sequential memories
 - PhD thesis "Limitations and Capacities of Weak Consistency Models" shows that causal consistency cannot solve mutual exclusion
 - Welch "Multi-writer regular" shows that weaker real-time consistency can solve mutual exclusion
 - Paper "Consistency requirements Lamport's Bakery for mutual exclusion"
 - What is the key to success in mutual exclusion?
 - Attiya "Laws of Order" paper

5. Characterization of Old-New Inversions in MWMR atomic registers
  - patterns
  - probabilistic analysis

6. Power of obstruction-free consensus vs. Power of wait-free consensus
 - less than
 - prove that directly: it is impossible to implement wait-free consensus object using just obstruction-free consensus objects and atomic registers.
 
7. Test-and-set-write (or CAS for compare-and-swap/compare-and-set) primitive in PNUTS
 - How is it implemented?
 - How to use it for optimistic concurrency control?

8. $k$-Atomic registers
 - single-round read cannot achieve atomicity
 - single-round read can achieve 2-atomicity
 - Q: Can single-round read achieve $k$-atomicity ($k \ge 3$)? [paper: PODC'04 How fast can a distributed atomic read be?]
 - to simulate a multi-writer $k$-atomicity register from single-writer $k$-atomicity ones (paper: Weak read-write registers)

9. Atomic/regular/safe registers + wait-free/lock-free/obstruction-free/contention free
 - paper "contention-free complexity"
 - paper "lock-free practically wait-free"
 
 10.  On Lamport's paper "On Interprocess Communication"
  - continue this work
  - paper "On specification of read/write shared registers"
 
 11.  Consistency conditions for multi-objects Distributed Operations
  - read the paper
  - relax it
  
 ## Transactions
 
 - Obstruction-free/lock-free (for read-only transactions) is practically wait-free???
 - NMSI implementation using version clock instead of vector clock
 - "The Power of Processor Consistency" in the context of transactions
   -  Transactional data race free (TDRF) and processor consistency in transactional system

 ## Consensus Problems
 
 ### Paxos
 
 1. Probabilistic analysis of "progress properties" of Paxos
 
 ## Papers and Reports
 
 ### Survey: Consistency Models in Distributed Shared Memory
 
 1. Quorum systems are mainly used for consistency models *with* real-time order. What about sequential consistency and causal consistency?
   - refer to [From causal consistency to sequential consistency]
  
 2. Think over the impossibility results/proofs and lower bounds from the perspective of "uncertainty" (and local knowledge)