Abstract
The aim of this invited talk is to try to stimulate research in the interesting and promising research direction of distributed verification. This distributed bears some similarities to the task of solving decision problems in the context of sequential computing. There, the study of decision problems proved very fruitful in establishing structured foundations for the theory. There are some signs that the study of distributed verification may be fruitful for the theory of distributed computing too.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its applications to self stabilization. Theoretical Computer Science 186(1-2), 199–230 (1997)
Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: 19th ACM Symp. on Theory of computing (STOC), pp. 230–240 (1987)
Awerbuch, B., Kutten, S., Peleg, D.: Competitive Distributed Job Scheduling. In: STOC 1992, pp. 571–580 (1992)
Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-Stabilization By Local Checking and Correction. In: Proc. IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 268–277 (1991)
Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: IEEE Symp. on Foundations of Computer Science, pp. 258–267 (1991)
Chandra, T.D., Hadzilacos, V., Toueg, S.: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4), 685–722 (1996)
Cook, S.: The complexity of theorem-proving procedures. In: Conference Record of 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM, New York (1971)
Dolev, S., Gouda, M., Schneider, M.: Requirements for silent stabilization. Acta Informatica 36(6), 447–462 (1999)
Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed Verification and Hardness of Distributed Approximation, http://arxiv.org/pdf/1011.3049
Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Computing 21(6), 1184–1192 (1992)
Dwork, C., Herlihy, M., Waarts, O.: Contention in shared memory algorithms. In: ACM PODC 1993, pp. 174–183 (1993)
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. In: Proc. 3rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 103–118 (1984)
Fraigniaud, P.: On distributed computational complexities: are you Volvo-driving or NASCAR-obsessed? In: ACM PODC 2010 (2010) (invited talk)
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32(2), 374–382 (1985)
Fraigniaud, P., Korman, A., Peleg, D.: Local distributed verification: complexity classes and complete problems (in progress)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66–77 (1983)
Garay, J., Kutten, S.A., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. SIAM J. Computing 27(1), 302–316 (1998)
Halpern, J., Moses, Y.: Knowledge and Common Knowledge in a Distributed Environment. J. ACM 37(3), 549–587 (1990)
Herlihy, M.: Wait-Free Synchronization. ACM Trans. Programming Languages and Systems 13(1), 124–149 (1991)
Herlihy, M., Shavit, N.: The Topological Structure of Asynchronous Computability. Journal of the ACM 46(6) (1999)
Kor, L., Korman, A., Peleg, D.: Tight Bounds For Distributed MST Verification (manuscript)
Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distributed Computing 20, 253–266 (2006); Extended abstract in PODC 2006
Korman, A., Kutten, S., Masuzawa, T.: Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST (submitted)
Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distributed Computing 22, 215–233 (2005); Extended abstract in PODC 2005
Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proc. of the 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 7–15 (2006)
Levin, L.: Universal search problems. Problemy Peredachi Informatsii 9(3), 265–266 (1973) (in Russian)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally? In: Proc. ACM Symp. on the Principles of Distributed Computing (PODC), pp. 300–309 (2004)
Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40–66 (1998)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Naor, M., Stockmeyer, L.: What can be computed locally? In: Proc. 25th ACM Symp. on Theory of Computing (STOC), pp. 184–193 (1993)
Saks, M., Zaharoglou, F.: Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM Journal on Computing 29(5) (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kutten, S. (2011). Distributed Decision Problems: The Locality Angle. In: Marchetti-Spaccamela, A., Segal, M. (eds) Theory and Practice of Algorithms in (Computer) Systems. TAPAS 2011. Lecture Notes in Computer Science, vol 6595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19754-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-19754-3_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19753-6
Online ISBN: 978-3-642-19754-3
eBook Packages: Computer ScienceComputer Science (R0)