User hengxin

25 votes

5 answers

931 views

Curious about computer-assisted NP-completeness proofs

asked Jan 31, 2015 at 5:37

19 votes

4 answers

11k views

Why is the consensus problem so important in distributed computing?

asked Dec 5, 2012 at 11:37

13 votes

1 answer

1k views

Correctness proofs of classic Paxos and Fast Paxos

asked Sep 24, 2014 at 9:00

11 votes

4 answers

1k views

Is there algorithmic mathematical analysis?

asked May 30, 2015 at 3:43

10 votes

1 answer

655 views

What are the major research issues in distributed transactions?

asked Dec 14, 2014 at 14:39

10 votes

2 answers

668 views

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

asked Feb 27, 2014 at 12:28

9 votes

1 answer

831 views

Is linearizability equivalent to consensus problem?

asked Apr 15, 2013 at 3:06

8 votes

2 answers

1k views

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

asked Dec 9, 2012 at 8:48

7 votes

4 answers

761 views

Explaining computer science algorithms/concepts/ideas using metaphors

asked Nov 2, 2014 at 9:21

7 votes

1 answer

147 views

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

asked Nov 23, 2015 at 7:21

6 votes

1 answer

461 views

Describing state machines mathematically

asked Jul 25, 2014 at 13:26

5 votes

0 answers

140 views

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

asked Aug 9, 2014 at 7:20

5 votes

1 answer

260 views

Confusion about a formal definition of PRAM consistency

asked Aug 21, 2018 at 2:53

4 votes

0 answers

137 views

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

asked Dec 6, 2012 at 13:19

4 votes

1 answer

495 views

Is This Scheduling Problem NP-Hard?

asked Sep 27, 2013 at 5:57

3 votes

1 answer

370 views

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

asked Dec 17, 2012 at 9:53

3 votes

0 answers

274 views

Atomic snapshot algorithms on tree-structured shared registers

asked Dec 29, 2013 at 4:05

3 votes

1 answer

321 views

Concurrent data structures vs. Distributed data structures

asked Jul 9, 2014 at 3:31

3 votes

1 answer

116 views

Lower bounds and impossibility results for distributed transactions

asked Dec 24, 2014 at 14:21

3 votes

0 answers

234 views

In what sense, does a safe register exist?

asked Jan 7, 2015 at 14:02

3 votes

1 answer

105 views

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

asked Mar 12, 2015 at 15:08

2 votes

1 answer

84 views

How to simulate sequential registers from causal ones?

asked Mar 25, 2015 at 3:39

2 votes

1 answer

462 views

Lower bound for finding repeated elements in sorted array

asked Apr 7, 2015 at 12:46

2 votes

0 answers

63 views

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

asked May 13, 2017 at 4:07

2 votes

0 answers

106 views

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

asked Mar 5, 2014 at 12:29

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?

asked Feb 19, 2014 at 9:11

1 vote

1 answer

122 views

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

asked Oct 15, 2014 at 2:44

1 vote

1 answer

189 views

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

asked Oct 1, 2013 at 5:28

1 vote

1 answer

225 views

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

asked Sep 20, 2013 at 12:34

1 vote

0 answers

121 views

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

asked Mar 13, 2019 at 1:54

Stack Exchange Network

31 Questions

Curious about computer-assisted NP-completeness proofs

Why is the consensus problem so important in distributed computing?

Correctness proofs of classic Paxos and Fast Paxos

Is there algorithmic mathematical analysis?

What are the major research issues in distributed transactions?

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

Is linearizability equivalent to consensus problem?

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

Explaining computer science algorithms/concepts/ideas using metaphors

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

Describing state machines mathematically

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

Confusion about a formal definition of PRAM consistency

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

Is This Scheduling Problem NP-Hard?

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

Atomic snapshot algorithms on tree-structured shared registers

Concurrent data structures vs. Distributed data structures

Lower bounds and impossibility results for distributed transactions

In what sense, does a safe register exist?

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

How to simulate sequential registers from causal ones?

Lower bound for finding repeated elements in sorted array

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

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

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

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

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

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

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