×

Wang tilings and distributed verification on anonymous torus networks. (English) Zbl 0870.68028

Summary: Consider \(n^2\) processors arranged in an \(n\times n\) torus network in which each processor is connected by direct communication channels with its four neighbours. This paper studies the following verification problem on anonymous \(n\times n\) torus networks: verify whether the network is oriented; that is, verify whether there is an agreement, among all processors, on a consistent channel labelling. The problem is to be solved by a distributed algorithm executed by the processors themselves.
If processors can label their channels arbitrarily, then there are network labellings that are not oriented but, to the processors, are indistinguishable from ones that are oriented. Hence there is no deterministic distributed verification algorithm. However, a verification algorithm does exist if the initial labellings are suitably restricted. We describe the restrictions placed on the initial labellings by subsets of the permutation group \(S_4\).
We show that the existence of an algorithm for verification is equivalent to the existence of certain tilings of the torus with Wang tiles. Using this equivalence, we have determined the existence of a distributed algorithm for the verification problem for all \(n\times n\) torus networks for an important class of restrictions, the subgroups of \(S_4\).

MSC:

68M99 Computer system organization
68Q60 Specification and verification (program logics, model checking, etc.)

Software:

Grail
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Attiya, H., Snir, M., Warmuth, M., Computing on an Anonymous Ring,Journal of the ACM, Vol. 35, No. 4 (1988), pp. 845–875. · Zbl 0662.68035 · doi:10.1145/48014.48247
[2] Beame, P. W., Bodlaender, H. L., Computing on Transitive Networks: The Torus, in Monien, B., Cori, R., editors,Proceedings of the Sixth Annual Symposium on Theoretical Aspects of Computer Science, (1989), pp. 294–303.
[3] F. J. Budden,The Fascination of Groups, Cambridge University Press, Cambridge, 1972. · Zbl 0238.20001
[4] Grünbaum, B., Shephard, G. C.,Tilings and Patterns, Freeman, San Francisco, CA, 1987. · Zbl 0601.05001
[5] Harary, F., Wilcox, G. W., Boolean Operations on Graphs,Mathematica Scandinavica, Vol. 20 (1967), pp. 41–51. · Zbl 0152.22801
[6] Korach, E., Moran, S., Zaks, S., Tight Upper and Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors, Technical Report TR-423, Department of Computer Science, Technion, July 1986. · Zbl 0681.68067
[7] Kranakis, E., Krizanc, D., Distributed Computing on Anonymous Hypercube Networks,Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing (1991), pp. 722–729.
[8] Norris, N., Universal Covers of Edge-Labelled Digraphs: Isomorphism to Depthn 1 Implies Isomorphism to all Depths,Discrete Applied Mathematics, Vol. 56, No. 1 (January 1995), pp. 61–74. · Zbl 0815.68074 · doi:10.1016/0166-218X(93)E0133-J
[9] Peterson, G. L., Efficient Algorithms for Elections in Meshes and Complete Networks, Technical Report TR-140, Department of Computer Science, University of Rochester, July 1985.
[10] Raymond, D. R., Wood, D., Grail: Engineering Automata in C++, Technical Report CS-93-01, Department of Computer Science, University of Waterloo, January 1993.
[11] Santoro, N., Sense of Direction, Topological Awareness and Communication Complexity,SIGACT News, Vol. 16, No. 2 (Summer 1984), pp. 50–56. · Zbl 0543.68020 · doi:10.1145/1008959.1008961
[12] Syrotiuk, V. R., Wang Tilings and Distributed Orientation on Anonymous Torus Networks, Ph.D. Thesis, Department of Computer Science, University of Waterloo, 1992.
[13] Syrotiuk, V. R., Colbourn, C. J., Pachl, J., Wang Tilings and Distributed Orientation on Anonymous Torus Networks,Proceedings of the Seventh International Workshop on Distributed Algorithms (1993), pp. 264–278. · Zbl 0870.68028
[14] Syrotiuk, V.R., Colbourn, C.J., Klarner, D.A., Pachl, J., Characterizing Tilings Using Finite Automata,Proceedings of the Third International Workshop on Polyominoes and Tilings (1994), pp. 11–30.
[15] Tel, G., Network Orientation, Technical Report RUU-CS-91-8, Department of Computer Science, Utrecht University, March 1991. · Zbl 0822.68046
[16] Wang, H., Notes on a Class of Tiling Problems,Fundamenta Mathematicae, Vol. 82 (1975), pp. 295–305. · Zbl 0301.02043
[17] Yamashita, M., Kameda, T., Computing on an Anonymous Network: Part I–Characterizing the Solvable Cases. Part II–Decision and Membership Problems.IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 1 (January 1996), pp. 69–96. · Zbl 05106556 · doi:10.1109/71.481599
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.