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.
Similar content being viewed by others
References
Angluin, D.: Local and global properties in netwroks of processors. In: Proc. 12th ACM Symp. on Theory of Computing, pp. 82–93 (1980)
Attiya H., Gorbach A., Moran S.: Computing in totally anon- ymous asynchronous shared memory systems. Inf Comput 173(2), 162–183 (2002)
Attyia H., Snir M., Warmuth M.K.: Computing on an anonymous ring. J. ACM 35(4), 845–875 (1988)
Bellman R.: On a routing problem. Quart. Appl. Math. 16(1), 87–90 (1958)
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)
Chang E., Roberts R.: An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun. ACM 22(5), 281–283 (1979)
Constable R.L. et al.: Implementing Mathematics with the Nuprl Proof Development System. Prentice-Hall, NJ (1986)
Dwork C., Moses Y.: Knowledge and common knowledge in a Byzantine environment: crash failures. Inf. Comput. 88(2), 156–186 (1990)
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)
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)
Fagin R., Halpern J.Y., Moses Y., Vardi M.Y.: Reasoning About Knowledge. MIT Press, Cambridge (1995)
Fagin R., Halpern J. Y., Moses Y., Vardi M. Y.: Knowledge-based programs. Distrib. Comput. 10(4), 199–225 (1997)
Ford L.R., Fulkerson D.R.: Flows in Networks. Princeton University Press, Princeton, NJ (1962)
Friedman N., Halpern J.Y.: Modeling belief in dynamic systems. Part I: foundations. Artif. Intell. 95(2), 257–316 (1997)
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)
Grove A.J.: Naming and identity in epistemic logic II: a first-order logic for naming. Artif. Intell. 74(2), 311–350 (1995)
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)
Hadzilacos, V.: A knowledge-theoretic analysis of atomic commitment protocols. In Proc. 6th ACM Symp. on Principles of Database Systems, pp. 129–134 (1987)
Halpern J.Y., Moses Y.: Using counterfactuals in knowl- edge-based programming. Distrib. Comput. 17(2), 91–106 (2004)
Halpern J.Y., Moses Y., Waarts O.: A characterization of eventual Byzantine agreement. SIAM J. Comput. 31(3), 838–865 (2001)
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)
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)
Le Lann, G.: Distributed systems–towards a formal approach. In: IFIP Congress, vol. 7, pp. 155–160 (1977)
Lewis D. K.: Counterfactuals. Harvard University Press, Cambridge, Mass (1973)
Lynch N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1997)
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
Mazer, M.S., Lochovsky, F.H.: Analyzing distributed commitment by reasoning about knowledge. Technical Report CRL 90/10, DEC-CRL (1990)
Milner R.: Communication and Concurrency. Prentice Hall, Hertfordshire (1989)
Moses, Y., Kislev, O.: Knowledge-oriented programming. In: Proc. 12th ACM Symp. on Principles of Distributed Computing, pp. 261–270 (1993)
Moses, Y., Roth, G.: On reliable message diffusion. In: Proc. 8th ACM Symp. on Principles of Distributed Computing, pp. 119–128 (1989)
Moses Y., Tuttle M. R.: Programming simultaneous actions using common knowledge. Algorithmica 3, 121–169 (1988)
Peterson G.L.: An O(nlogn) unidirectional distributed algorithm for the circular extrema problem. ACM Trans. Programm. Lang. Syst. 4(4), 758–762 (1982)
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)
Stulp F., Verbrugge R.: A knowledge-based algorithm for the Internet protocol (TCP). Bull. Econ. Res. 54(1), 69–94 (2002)
Yamashita M., Kameda T.: Computing on anonymous networks. I. Characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69–89 (1996)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
Work supported in part by NSF under grants CTC-0208535, ITR-0325453, and IIS-0534064, by ONR under grant N00014-02-1-0455, by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grants N00014-01-1-0795 and N00014-04-1-0725, and by AFOSR under grants F49620-02-1-0101 and FA9550-05-1-0055.
This work was done while the author was at Cornell University.
Rights and permissions
About this article
Cite this article
Halpern, J.Y., Petride, S. A knowledge-based analysis of global function computation. Distrib. Comput. 23, 197–224 (2010). https://doi.org/10.1007/s00446-010-0111-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-010-0111-7