2 problems

0 votes0 replies0 views
Extension of the Corollary 4 storage lower bound to bounded-phase algorithms
Consider shared-memory emulation algorithms with a bounded number of phases, at most one of which sends a value-dependent message of size $\Theta(|\mathcal{V}|)$ ; the other value-d…
Conjectureopendistributed-storage information-theoretic-lower-bounds shared-memory-emulationarXiv posted 2 days ago
0 votes0 replies1 view
Extension of the Theorem 4 storage lower bound to two-phase algorithms
Theorem 4 concerns shared-memory emulation algorithms whose value-dependent messages satisfy its stated assumptions. Some algorithms instead send value-dependent messages in two ph…
Conjectureopendistributed-storage information-theoretic-lower-bounds shared-memory-emulationarXiv posted 2 days ago

Extension of the Corollary 4 storage lower bound to bounded-phase algorithms