Ignorance is Bliss (for Proving Impossibility)

摘要

This talk surveys techniques for proving uncomputability results and lower bounds in message passing models. An uncomputability result tells us that a certain problem cannot be solved in a particular model and a lower bound tells us that a certain problem cannot be solved in a particular model when insufficient resources are available. All of these impossibility results hinge on the processes' continued ignorance of input values, network parameters, or one another's states. Ignorance can also arise from asynchrony and faults.