Research Questions, Ideas, and Progress

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"

   1. On Lamport's paper "On Interprocess Communication"
   2. continue this work

   3. paper "On specification of read/write shared registers"

   4. Consistency conditions for multi-objects Distributed Operations

   5. read the paper
   6. 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)