English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

To study the distributed task solvability, Goubault, Ledent, and Rajsbaumdevised a model of dynamic epistemic logic that is equivalent to thetopological model for distributed computing. In the logical model, theunsolvability of a particular distributed task can be proven by finding aformula, called logical obstruction. This logical method is very appealingbecause the concrete formulas that prevent to solve task would haveimplications of intuitive factors for the unsolvability. However, it has notbeen well studied when a logical obstruction exists and how to systematicallyconstruct a concrete logical obstruction formula, if any. In addition, it isproved that there are some tasks that are solvable but do not admit logicalobstructions.  In this paper, we propose a method to prove the non-existence of logicalobstructions to the solvability of distributed tasks, based on the technique ofsimulation. Moreover, we give a method to determine whether a logicalobstruction exists or not for a finite protocol and a finite task, and if itexists, construct a concrete obstruction. Using this method, we demonstratethat the language of the standard epistemic logic, without distributedknowledge, does not admit logical obstruction to the solvability of $k$-setagreement tasks. We also show that there is no logical obstruction formulti-round immediate snapshot even in the language of epistemic logic withdistributed knowledge. In addition, for the know-all model, we provide aconcrete obstruction formula that shows the unsolvability of the $k$-setagreement task.

Determining Existence of Logical Obstructions to the Distributed Task Solvability