On Distributed Verification
Amos Korman1 and Shay Kutten1
Faculty of IE&M, Technion, Haifa 32000, Israel
Abstract:
This paper describes the invited talk given at the 8th International Conference on
Distributed Computing and Networking (ICDCN 2006), at the Indian Institute of Technology
Guwahati, India. This talk was intended to give a partial survey and to motivate further
studies of distributed verification. To serve the purpose of motivating, we allow ourselves
to speculate freely on the potential impact of such research.
In the context of sequential computing, it is common to assume that the task of verifying
a property of an object may be much easier than computing it (consider, for example,
solving an NP-Complete problem versus verifying a witness). Extrapolating from the impact
the separation of these two notions (computing and verifying) had in the context of
sequential computing, the separation may prove to have a profound impact on the field of
distributed computing as well. In addition, in the context of distributed computing, the
motivation for the separation seems even stronger than in the centralized sequential case.
In this paper we explain some motivations for specific definitions,
survey some very related notions and their motivations in the literature, survey some
examples for problems and solutions, and mention some additional general results such as
general algorithmic methods and general lower bounds. Since this paper is mostly intended
to “give a taste” rather than be a comprehensive survey, we apologize to authors of
additional related papers that we did not mention or detailed.