hengxin's user avatar
hengxin's user avatar
hengxin's user avatar
hengxin
  • Member for 11 years, 2 months
  • Last seen more than a week ago
25 votes
5 answers
918 views

Curious about computer-assisted NP-completeness proofs

19 votes
4 answers
11k views

Why is the consensus problem so important in distributed computing?

13 votes
1 answer
1k views

Correctness proofs of classic Paxos and Fast Paxos

11 votes
4 answers
1k views

Is there algorithmic mathematical analysis?

10 votes
1 answer
640 views

What are the major research issues in distributed transactions?

10 votes
2 answers
646 views

Why is linearizability a safety property and why are safety properties closed sets?

9 votes
1 answer
780 views

Is linearizability equivalent to consensus problem?

8 votes
2 answers
1k views

Is there some mathematical closed form (or somewhat tight asymptotic one) for "Google Eggs Puzzle"?

7 votes
4 answers
729 views

Explaining computer science algorithms/concepts/ideas using metaphors

7 votes
1 answer
145 views

Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990]

6 votes
1 answer
456 views

Describing state machines mathematically

5 votes
0 answers
140 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

5 votes
1 answer
234 views

Confusion about a formal definition of PRAM consistency

4 votes
0 answers
136 views

What are the parts of consistency model playing in hardware, operating system, and programming language?

4 votes
1 answer
486 views

Is This Scheduling Problem NP-Hard?

3 votes
1 answer
366 views

How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

3 votes
0 answers
267 views

Atomic snapshot algorithms on tree-structured shared registers

3 votes
1 answer
293 views

Concurrent data structures vs. Distributed data structures

3 votes
1 answer
114 views

Lower bounds and impossibility results for distributed transactions

3 votes
0 answers
227 views

In what sense, does a safe register exist?

3 votes
1 answer
103 views

Results about computability power or limitations of shared read/write registers

2 votes
1 answer
82 views

How to simulate sequential registers from causal ones?

2 votes
1 answer
446 views

Lower bound for finding repeated elements in sorted array

2 votes
0 answers
63 views

Studying the hardness of polynomial-time approximability using the concept of stability of approximation

2 votes
0 answers
105 views

Are the sets of executions of data-race free programs equal, when run on causal memory and on sequentially consistent memory respectively?

1 vote
0 answers
56 views

What is the staleness in this execution of the $k$-atomic multi-writer register construction from $k$-atomic single-writer ones?

1 vote
1 answer
120 views

Concurrent transactions satisfying "serializability" but not "snapshot isolation"

1 vote
1 answer
187 views

Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?

1 vote
1 answer
225 views

How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

1 vote
0 answers
110 views

Confusion about the visibility and arbitration relations in a formal framework for distributed consistency models