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

1. Simulations of shared registers without "real-time" semantics:

• causal consistency $\Rightarrow$ sequential consistency

1. Probabilistic quorum systems for multi-writer atomic registers

• definition
• probabilistic analysis
• refer to [Item 1] and the paper "Randomized registers and iterative algorithms"

1. 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

1. Characterization of Old-New Inversions in MWMR atomic registers

• patterns
• probabilistic analysis

1. 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.

1. 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?

1. $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)

1. 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"

• continue this work
• paper "On specification of read/write shared registers"

1. 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]

1. Think over the impossibility results/proofs and lower bounds from the perspective of "uncertainty" (and local knowledge)