A knowledge-based analysis of global function computation. (English) Zbl 1231.68080
Summary: Consider a distributed system \(N\) in which each agent has an input value and each communication link has a weight. Given a global function, that is, a function \(f\) whose value depends on the whole network, the goal is for every agent to eventually compute the value \(f (N)\). We call this problem global function computation. Various solutions for instances of this problem, such as Boolean function computation, leader election, (minimum) spanning tree construction, and network determination, have been proposed, each under particular assumptions about what processors know about the system and how this knowledge can be acquired. We give a necessary and sufficient condition for the problem to be solvable that generalizes a number of well-known results [H. Attyia, M. Snir and M. K. Warmuth, J. Assoc. Comput. Mach. 35, No. 4, 845–875 (1988; Zbl 0662.68035); M. Yamashita and T. Kameda, IEEE Trans. Parallel Distrib. Syst. 7, No. 1, 69–89 (1996); ibid. 10, No. 9, 878–887 (1999)]. We then provide a knowledge-based (kb) program that solves global function computation whenever possible. Finally, we improve the message overhead inherent in our initial kb program by giving a counterfactual belief-based program that also solves the global function computation whenever possible, but where agents send messages only when they believe it is necessary to do so. The latter program is shown to be implemented by a number of well-known algorithms for solving leader election.
MSC:
| 68M14 | Distributed systems |
| 68T27 | Logic in artificial intelligence |
| 68T30 | Knowledge representation |
Keywords:
distributed agent system; global function computation; leader election; nowledge-based (kb) programCitations:
Zbl 0662.68035Software:
NuprlReferences:
| [1] | Angluin, D.: Local and global properties in netwroks of processors. In: Proc. 12th ACM Symp. on Theory of Computing, pp. 82–93 (1980) |
| [2] | Attiya H., Gorbach A., Moran S.: Computing in totally anon- ymous asynchronous shared memory systems. Inf Comput 173(2), 162–183 (2002) · Zbl 1009.68012 · doi:10.1006/inco.2001.3119 |
| [3] | Attyia H., Snir M., Warmuth M.K.: Computing on an anonymous ring. J. ACM 35(4), 845–875 (1988) · Zbl 0662.68035 · doi:10.1145/48014.48247 |
| [4] | Bellman R.: On a routing problem. Quart. Appl. Math. 16(1), 87–90 (1958) · Zbl 0081.14403 |
| [5] | Bickford, M., Constable, R.L., Halpern, J.Y., Petride, S.: Knowledge-based synthesis of distributed systems using event structures. In: Proc. 11th Int. Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2004). Lecture Notes in Computer Science, vol. 3452, pp. 449–465. Springer (2005) · Zbl 1108.68491 |
| [6] | Chang E., Roberts R.: An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun. ACM 22(5), 281–283 (1979) · Zbl 0394.68023 · doi:10.1145/359104.359108 |
| [7] | Constable R.L. et al.: Implementing Mathematics with the Nuprl Proof Development System. Prentice-Hall, NJ (1986) |
| [8] | Dwork C., Moses Y.: Knowledge and common knowledge in a Byzantine environment: crash failures. Inf. Comput. 88(2), 156–186 (1990) · Zbl 0705.68019 · doi:10.1016/0890-5401(90)90014-9 |
| [9] | Engelhardt K., van der Meyden R., Moses Y.: A program refine- ment framework supporting reasoning about knowledge and time. In: Tiuryn, J. (ed.) Proc. Foundations of Software Science and Computation Structures (FOSSACS 2000), pp. 114–129. Springer, Berlin/New York (2000) · Zbl 0961.68031 |
| [10] | Engelhardt, K., van der Meyden, R., Moses, Y.: A refinement theory that supports reasoning about knowledge and time for synchronous agents. In: Proc. International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, pp. 125–141. Springer, Berlin/New York (2001) · Zbl 1275.68137 |
| [11] | Fagin R., Halpern J.Y., Moses Y., Vardi M.Y.: Reasoning About Knowledge. MIT Press, Cambridge (1995) · Zbl 0839.68095 |
| [12] | Fagin R., Halpern J. Y., Moses Y., Vardi M. Y.: Knowledge-based programs. Distrib. Comput. 10(4), 199–225 (1997) · Zbl 1374.68102 · doi:10.1007/s004460050038 |
| [13] | Ford L.R., Fulkerson D.R.: Flows in Networks. Princeton University Press, Princeton, NJ (1962) · Zbl 0106.34802 |
| [14] | Friedman N., Halpern J.Y.: Modeling belief in dynamic systems. Part I: foundations. Artif. Intell. 95(2), 257–316 (1997) · Zbl 0894.68146 · doi:10.1016/S0004-3702(97)00040-4 |
| [15] | Gallager R.G., Humblet P.A., Spira P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Programm. Lang. Syst. 5(1), 66–77 (1983) · Zbl 0498.68040 · doi:10.1145/357195.357200 |
| [16] | Grove A.J.: Naming and identity in epistemic logic II: a first-order logic for naming. Artif. Intell. 74(2), 311–350 (1995) · Zbl 1012.03028 · doi:10.1016/0004-3702(95)98593-D |
| [17] | Grove A.J., Halpern J.Y.: Naming and identity in epistemic logics, Part I: the propositional case. J. Logic Comput. 3(4), 345–378 (1993) · Zbl 0808.03009 · doi:10.1093/logcom/3.4.345 |
| [18] | Hadzilacos, V.: A knowledge-theoretic analysis of atomic commitment protocols. In Proc. 6th ACM Symp. on Principles of Database Systems, pp. 129–134 (1987) |
| [19] | Halpern J.Y., Moses Y.: Using counterfactuals in knowl- edge-based programming. Distrib. Comput. 17(2), 91–106 (2004) |
| [20] | Halpern J.Y., Moses Y., Waarts O.: A characterization of eventual Byzantine agreement. SIAM J. Comput. 31(3), 838–865 (2001) · Zbl 1017.68007 · doi:10.1137/S0097539798340217 |
| [21] | Halpern J.Y., Zuck L.D.: A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols. J. ACM 39(3), 449–478 (1992) · Zbl 0799.68024 · doi:10.1145/146637.146638 |
| [22] | Johnson, R.E., Schneider, F.B.: Symmetry and similarity in distributed systems. In Proc. 4th ACM Symp. on Principles of Distributed Computing, pp. 13–22 (1985) |
| [23] | Le Lann, G.: Distributed systems–towards a formal approach. In: IFIP Congress, vol. 7, pp. 155–160 (1977) |
| [24] | Lewis D. K.: Counterfactuals. Harvard University Press, Cambridge, Mass (1973) |
| [25] | Lynch N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1997) |
| [26] | Lynch N.A., Tuttle M.R.: An introduction to input/output automata.. CWI Quarterly 2(3), 219–246 (1989) Also available as MIT Technical Memo MIT/LCS/TM-373 |
| [27] | Mazer, M.S., Lochovsky, F.H.: Analyzing distributed commitment by reasoning about knowledge. Technical Report CRL 90/10, DEC-CRL (1990) |
| [28] | Milner R.: Communication and Concurrency. Prentice Hall, Hertfordshire (1989) · Zbl 0683.68008 |
| [29] | Moses, Y., Kislev, O.: Knowledge-oriented programming. In: Proc. 12th ACM Symp. on Principles of Distributed Computing, pp. 261–270 (1993) · Zbl 1374.68075 |
| [30] | Moses, Y., Roth, G.: On reliable message diffusion. In: Proc. 8th ACM Symp. on Principles of Distributed Computing, pp. 119–128 (1989) |
| [31] | Moses Y., Tuttle M. R.: Programming simultaneous actions using common knowledge. Algorithmica 3, 121–169 (1988) · Zbl 0646.68031 · doi:10.1007/BF01762112 |
| [32] | Peterson G.L.: An O(nlogn) unidirectional distributed algorithm for the circular extrema problem. ACM Trans. Programm. Lang. Syst. 4(4), 758–762 (1982) · Zbl 0489.68040 · doi:10.1145/69622.357194 |
| [33] | Stalnaker R.C.: A semantic analysis of conditional logic. In: Rescher, N. (ed.) Studies in Logical Theory, pp. 98–112. Oxford University Press, Oxford, UK (1968) |
| [34] | Stulp F., Verbrugge R.: A knowledge-based algorithm for the Internet protocol (TCP). Bull. Econ. Res. 54(1), 69–94 (2002) · doi:10.1111/1467-8586.00140 |
| [35] | Yamashita M., Kameda T.: Computing on anonymous networks. I. Characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69–89 (1996) · doi:10.1109/71.481599 |
| [36] | Yamashita M., Kameda T.: Leader election problem on networks in which processor identity numbers are not distinct. IEEE Trans. Parallel Distrib. Syst. 10(9), 878–887 (1999) · doi:10.1109/71.798313 |
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.
