Dashboard

Now you are in the subtree of Distributed Computing project. 

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)