Abstract
This paper studies notions of locality that are inherent to the specification of a distributed task and independent of the computing environment, in a shared memory wait-free system.
A locality property called projection-closed is identified, that completely characterizes tasks that are wait-free checkable. A task \(T =(\ensuremath{\mathcal{I}} ,\ensuremath{\mathcal{O}} ,\Delta)\) is checkable if there exists a wait-free distributed algorithm that, given \(s\in\ensuremath{\mathcal{I}} \) and \(t\in\ensuremath{\mathcal{O}} \), determines whether t ∈ Δ(s), i.e., if t is a valid output for s according to the specification of T. Moreover, determining whether a projection-closed task is wait-free solvable remains undecidable, and hence this is a rich class of tasks.
A stronger notion of locality considers tasks where the outputs look identically to the inputs at every vertex (input value of a process). A task \(T= (\ensuremath{\mathcal{I}} ,\ensuremath{\mathcal{O}} ,\Delta)\) is said to be locality-preserving if \(\ensuremath{\mathcal{O}} \) is a covering complex of \(\ensuremath{\mathcal{I}} \). This topological property yields obstacles for wait-free solvability different in nature from the classical agreement impossibility results. On the other hand, locality-preserving tasks are projection-closed and therefore always wait-free checkable. A classification of locality-preserving tasks in term of their relative computational power is provided. A correspondence between locality-preserving tasks and subgroups of the edgepath group of an input complex shows the existence of hierarchies of locality-preserving tasks, each one containing at the top the universal task (induced by the universal covering complex), and at the bottom the trivial identity task.
Work supported in part by a CONACYT/CNRS grant.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Angluin, D.: Local and Global Properties in Networks of Processors (Extended Abstract). In: 12th ACM Symp. on Theory of Computing (STOC), pp. 82–93 (1980)
Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuck, R.: Renaming in Asynchronous Environment. Journal of the ACM 37(3), 524–548 (1990)
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley, Chichester (2004)
Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by Local Checking and Correction. In: 32nd IEEE Symp. on 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: 32nd IEEE Symp. on Foundations of Computer Science (FOCS), pp. 258–267 (1991)
Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: 29th ACM Symp. on Principles of Distributed Computing (PODC), pp. 410–419 (2010)
Blum, M., Kannan, S.: Designing Programs that Check Their Work. J. ACM 42(1), 269–291 (1995)
Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3), 549–595 (1993)
Chalopin, J., Métivier, Y.: On the Power of Synchronization Between two Adjacent Processes. Distributed Computing 23(3), 177–196 (2010)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70(1), 32–53 (1986)
Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed Verification and Hardness of Distributed Approximation. In: 43rd ACM Symp. on Theory of Computing, STOC (2011)
Dolev, D., Lynch, N., Pinter, S., Stark, E., Weihl, W.: Reaching Approximate Agreement in the Presence of Faults. J. ACM 33(3), 499–516 (1986)
Ergün, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-Checkers. J. Comput. Syst. Sci. 60(3), 717–751 (2000)
Fischer, M., Lynch, N., Paterson, M.: Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32(2), 374–382 (1985)
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Communication algorithms with advice. J. Comput. Syst. Sci. 76(3-4), 222–232 (2010)
Fraigniaud, P., Korman, A., Peleg, D.: Local Distributed Decision. arXiv:1011.2152
Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and Checkability in Wait-free Computing. technical report, http://hal.archives-ouvertes.fr/hal-00605244/en/
Franklin, M., Garay, J.A., Yung, M.: Self-Testing/Correcting Protocols. In: Jayanti, P. (ed.) DISC 1999. LNCS, vol. 1693, pp. 269–284. Springer, Heidelberg (1999)
Freund, Y., Kearns, M., Ron, D., Rubinfeld, R., Schapire, R., Sellie, L.: Efficient Learning of Typical Finite Automata from Random Walks. Inf. Comput. 138(1), 23–48 (1997)
Gafni, E., Koutsoupias, E.: Three-Processor Tasks Are Undecidable. SIAM J. Comput. 28(3), 970–983 (1999)
Goldreich, O., Goldwasser, S., Shari, Ron, D.: Property Testing and its Connection to Learning and Approximation. J. ACM 45(4), 653–750 (1998)
Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.: A (De)constructive Approach to Program Checking. In: 40th ACM Symp. on Theory of Computing (STOC), pp. 143–152 (2008)
Goos, M., Suomela, J.: Locally checkable proofs. In: 30th ACM Symp. on Principles of Distributed Computing, PODC (2011)
Herlihy, M., Rajsbaum, S.: The Decidability of Distributed Decision Tasks. In: 29th ACM Symp. on the Theory of Computing (STOC), pp. 589–598 (1997)
Herlihy, M., Rajsbaum, S.: A Classification of Wait-Free Loop Agreement Tasks. Theor. Comput. Sci. 291(1), 55–77 (2003)
Herlihy, M., Shavit, N.: The Topological Structure of Asynchronous Computability. J. ACM 46(6), 858–923 (1999)
Korman, A., Kutten, S., Peleg, D.: Proof Labeling Schemes. Distributed Computing 22, 215–233 (2010)
Korman, A., Sereni, J.-S., Viennot, L.: Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge. In: 30th ACM Symp. on Principles of Distributed Computing, PODC (2011)
Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 7–15 (2006)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Lipton, R.: New Directions in Testing. In: DIMACS Workshop on Distributed computing and Cryptography, vol. 2, pp. 191–202 (1991)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers, San Francisco (1996)
Mazurkiewicz, A.: Distributed Enumeration. Inf. Process. Lett. 61, 233–239 (1997)
Naor, M., Stockmeyer, L.: What can be Computed Locally? SIAM J. Comput. 24(6), 1259–1277 (1995)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Rotman, J.: Covering Complexes with Applications to Algebra. Rocky Mountain J. of Mathematics 3(4), 641–674 (1973)
Rubinfeld, R.: Designing Checkers for Programs that Run in Parallel. Algorithmica 15(4), 287–301 (1996)
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
Fraigniaud, P., Rajsbaum, S., Travers, C. (2011). Locality and Checkability in Wait-Free Computing. In: Peleg, D. (eds) Distributed Computing. DISC 2011. Lecture Notes in Computer Science, vol 6950. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24100-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-24100-0_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24099-7
Online ISBN: 978-3-642-24100-0
eBook Packages: Computer ScienceComputer Science (R0)