A knowledge-based analysis of global function computation
Pages 136 - 150
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 [3, 28, 29]. We then provide a knowledge-based (kb) program (like those of Fagin, Halpern, Moses, and Vardi [8,9]) 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 [15] 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]
D. Angluin. Local and global properties in netwroks of processors. In Proc. 12th ACM Symp. on Theory of Computing, pages 82-93, 1980.
[2]
H. Attyia, A. Gorbach, and S. Moran. Computing in totally anonymous asynchronous shared memory systems. Information and Computation, 173(2):162-183, 2002.
[3]
H. Attyia, M. Snir, and M. K. Warmuth. Computing on an anonymous ring. Journal of ACM, 35(4):845-875, 1988.
[4]
R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958.
[5]
M. Bickford, R. L. Constable, J. Y. Halpern, and S. Petride. Knowledge-based synthesis of distributed systems using event structures. In Proc. 11th Int. Conf. on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2004), Lecture Notes in Computer Science, vol. 3452, pages 449-465. Springer-Verlag, 2005.
[6]
E. Chang and R. Roberts. An improved algorithm for decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 22(5):281-283, 1979.
[7]
C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: crash failures. Information and Computation, 88(2):156-186, 1990.
[8]
R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, Cambridge, Mass., 1995. A revised paperback edition was published in 2003.
[9]
R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Knowledge-based programs. Distributed Computing, 10(4):199-225, 1997.
[10]
L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
[11]
R. G. Gallager, P. A. Humblet, and P.M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and Systems, 5(1):66-77, 1983.
[12]
A. J. Grove. Naming and identity in epistemic logic II: a first-order logic for naming. Artificial Intelligence, 74(2):311-350, 1995.
[13]
A. J. Grove and J. Y. Halpern. Naming and identity in epistemic logics, Part I: the propositional case. Journal of Logic and Computation, 3(4):345-378, 1993.
[14]
V. Hadzilacos. A knowledge-theoretic analysis of atomic commitment protocols. In Proc. 6th ACM Symp. on Principles of Database Systems, pages 129-134, 1987.
[15]
J. Y. Halpern and Y. Moses. Using counterfactuals in knowledge-based programming. Distributed Computing, 17(2):91-106, 2004.
[16]
J. Y. Halpern, Y. Moses, and O. Waarts. A characterization of eventual Byzantine agreement. SIAM Journal on Computing, 31(3):838-865, 2001.
[17]
J. Y. Halpern and L. D. Zuck. A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols. Journal of the ACM, 39(3):449-478, 1992.
[18]
R. E. Johnson and F. B. Schneider. Symmetry and similarity in distributed systems. In Proc. 4th ACM Symp. on Principles of Distributed Computing, pages 13-22, 1985.
[19]
Gerard Le Lann. Distributed systems-towards a formal approach. In IFIP Congress, volume 7, pages 155-160, 1977.
[20]
D. K. Lewis. Counterfactuals. Harvard University Press, Cambridge, Mass., 1973.
[21]
N.A. Lynch. Distributed Algorithms. Morgan Kaufmann, San Francisco, 1997.
[22]
M. S. Mazer and F. H. Lochovsky. Analyzing distributed commitment by reasoning about knowledge. Technical Report CRL 90/10, DEC-CRL, 1990.
[23]
R. Milner. Communication and Concurrency. Prentice Hall, Hertfordshire, 1989.
[24]
Y. Moses and G. Roth. On reliable message diffusion. In Proc. 8th ACM Symp. on Principles of Distributed Computing, pages 119-128, 1989.
[25]
G. L. Peterson. An O(n log n) unidirectional distributed algorithm for the circular extrema problem. ACM Trans. on Programming Languages and Systems, 4(4):758-762, 1982.
[26]
R. C. Stalnaker. A semantic analysis of conditional logic. In N. Rescher, editor, Studies in Logical Theory, pages 98-112. Oxford University Press, 1968.
[27]
F. Stulp and R. Verbrugge. A knowledge-based algorithm for the Internet protocol (TCP). Bulletin of Economic Research, 54(1):69-94, 2002.
[28]
M. Yamashita and T. Kameda. Computing on anonymous networks. I. Characterizing the solvable cases. IEEE Trans. on Parallel and Distributed Systems, 7(1):69-89, 1996.
[29]
M. Yamashita and T. Kameda. Leader election problem on networks in which processor identity numbers are not distinct. IEEE Trans. on Parallel and Distributed Systems, 10(9):878-887, 1999.
- A knowledge-based analysis of global function computation
Recommendations
A knowledge-based analysis of global function computation
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 ...
Finding Global Minima with a Computable Quasi-filled Function for Constrained Global Optimization
APWCS '10: Proceedings of the 2010 Asia-Pacific Conference on Wearable Computing SystemsA novel quasi-filled function approach is proposed in this paper for a constrained global minimization problem. Firstly, the definition of quasi-filled function is given, a quasi-filled function is constructed, and then a quasi-filled function algorithm ...
A Radial Basis Function Method for Global Optimization
We introduce a method that aims to find the global minimum of a continuous nonconvex function on a compact subset of \dR d. It is assumed that function evaluations are expensive and that no additional information is available. Radial basis function ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- BGU: BGU
- Swedish Institute of Computer Science: Swedish Institute of Computer Science
- Sun Microsystems
- Intel: Intel
- Microsoft Research: Microsoft Research
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 18 September 2006
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 18 Feb 2025