A knowledge-based analysis of global function computation
Abstract
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 (Attyia et al. in J ACM 35(4):845---875, 1988; Yamashita and Kameda in IEEE Trans Parallel Distrib Syst 7(1):69---89, 1996; Yamashita and Kameda in IEEE Trans Parallel Distrib Syst 10(9):878---887, 1999). We then provide a knowledge-based (kb) program (like those of Fagin et al. (Reasoning about knowledge, MIT Press, Cambridge, 1995, Distrib Comput 10(4):199---225, 1997)) 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 (Halpern and Moses in Distrib Comput 17(2):91---106, 2004) 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.
References
[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)
[3]
Attyia H., Snir M., Warmuth M.K.: Computing on an anonymous ring. J. ACM 35(4), 845---875 (1988)
[4]
Bellman R.: On a routing problem. Quart. Appl. Math. 16(1), 87---90 (1958)
[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)
[6]
Chang E., Roberts R.: An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun. ACM 22(5), 281---283 (1979)
[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)
[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)
[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)
[11]
Fagin R., Halpern J.Y., Moses Y., Vardi M.Y.: Reasoning About Knowledge. MIT Press, Cambridge (1995)
[12]
Fagin R., Halpern J. Y., Moses Y., Vardi M. Y.: Knowledge-based programs. Distrib. Comput. 10(4), 199---225 (1997)
[13]
Ford L.R., Fulkerson D.R.: Flows in Networks. Princeton University Press, Princeton, NJ (1962)
[14]
Friedman N., Halpern J.Y.: Modeling belief in dynamic systems. Part I: foundations. Artif. Intell. 95(2), 257---316 (1997)
[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)
[16]
Grove A.J.: Naming and identity in epistemic logic II: a first-order logic for naming. Artif. Intell. 74(2), 311---350 (1995)
[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)
[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)
[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)
[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)
[29]
Moses, Y., Kislev, O.: Knowledge-oriented programming. In: Proc. 12th ACM Symp. on Principles of Distributed Computing, pp. 261---270 (1993)
[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)
[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)
[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)
[35]
Yamashita M., Kameda T.: Computing on anonymous networks. I. Characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69---89 (1996)
[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)
- A knowledge-based analysis of global function computation
Recommendations
A knowledge-based analysis of global function computation
DISC'06: Proceedings of the 20th international conference on Distributed ComputingConsider 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 ...
Knowledge acquisition for knowledge-based engineering systems
This paper is essentially concerned with the development of formal representations of knowledge required prior to the development of knowledge-based engineering systems (KBESs). Initially, the paper provides a brief introduction to knowledge-based ...
Eliciting Knowledge and Transferring It Effectively to a Knowledge-Based System
The knowledge acquisition bottleneck impeding the development of expert systems is being alleviated by the development of computer-based knowledge acquisition tools. These work directly with experts to elicit knowledge, and structure it appropriately to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2010 Springer-Verlag.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 November 2010
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025