Skip to main content
2 votes

Two Generals' Problem - Thought Experiment

Let's say $a$ has gotten its second confirmation while $b$ only has one confirmation. $a$ sends an ack to $b$ to tell $b$ it has received the second message. Now, by your rule $a$ should start ...
proof-of-correctness's user avatar
1 vote

Communication complexity of Dyck language

TL;DR: $n \le C(f) \le n+1$. We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible