Moni Naor
Larry Stockmeyer
- 1.L. Adleman, Two theorems on random polynomial time, Proc. 19th IEEE Syrup. on Foundations of Computer Science, 1978, pp. 75-83.Google Scholar
Digital Library
- 2.Y. Afek, 2i. Kutten, and M. Yung, Local detection for global self stabilization, manuscript; preliminary version in Proc. 4th WDAG, LNCS 486, Springer-Verlag, 1991, pp. 15-28. Google ScholarDigital Library
- 3.B. Awerbuch, A.V. Goldberg, M. Luby, and S.A. Plotkin, Network decomposition and locality in distributed computation, Proc. 30th IEEE Syrup. on Foundations of Computer Science, 1989, pp. 364--369.Google ScholarDigital Library
- 4.K.M. Chandy and J. Misra, The drinking philosophers problem, A CM Trans. Programming Languages and Systems 6 (1984), pp. 632-646. Google ScholarDigital Library
- 5.M. Choy and A.K. Singh, Efficient fault tolerant algorithms for resource allocation in distributed systems, Proc. 24th A CM Syrup. on Theory o} Computing, 1992, pp. 593-602. Google ScholarDigital Library
- 6.R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control 70 (1986), pp. 32-53. Google ScholarDigital Library
- 7.G.N. Frederickson and N.A. Lynch, Electing a leader in a synchronous ring, J. Assoc. Comput. Mach. 34 (1987), pp. 98-115. Google ScholarDigital Library
- 8.A.V. Goldberg, S.A. Plotkin, and G.E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM J. Discrete Math. 1 (1989), pp. 434-446. Google ScholarDigital Library
- 9.N. Linial, Locality in distributed graph algorithms, SIAM J. Comput. 21 (1992), pp. 193-201. Google ScholarDigital Library
- 10.N.A. Lynch, Upper bounds for static resource allocation in a distributed system, J. Comput. System Sci. 23 (1981), pp. 254-278.Google ScholarCross Ref
- 11.S. Moran, M. Snir, and U. Manber, Applications of Ramsey's theorem to decision tree complexity, J. Assoc. Comput. Mach. 32 (1985), pp. 938-949. Google ScholarDigital Library
- 12.M. Naor and L. Stockmeyer, What can be computed locally?, IBM Research Report, in preparation.Google Scholar
- 13.A. Panconesi and A. Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proc. 24th A CM Syrup. on Theory of Computing, 1992, pp. 581-592. Google ScholarDigital Library
- 14.E. Styer and G.L. Peterson, Improved algorithms for distributed resource allocation, Proc. 7th ACM Symp. on Principles of Distributed Computing, 1988, pp. 105-116. Google ScholarDigital Library
- 15.A. C.-C. Yao, Should tables be sorted?, J. Assoc. Comput. Mach. 28 (1981), pp. 615-628. Google ScholarDigital Library
Index Terms
- What can be computed locally?
Recommendations
What Can Be Computed Locally?
The purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, ...
Can MIC find its place in the field of PDES?: An Early Performance Evaluation of PDES Simulator on Intel Many Integrated Cores Coprocessor
DS-RT 2015: Proceedings of the 19th International Symposium on Distributed Simulation and Real Time ApplicationsThe widespread utilization of many-core processors offers a good opportunity for Parallel Discrete Events Simulation (PDES) to obtain a better execution performance. As one of the newly introduced many-core processors, the Intel Xeon Phi coprocessor ...
Can Portability Improve Performance?: An Empirical Study of Parallel Graph Analytics
ICPE '15: Proceedings of the 6th ACM/SPEC International Conference on Performance EngineeringDue to increasingly large datasets, graph analytics - traversals, all-pairs shortest path computations, centrality measures, etc. - are becoming the focus of high-performance computing (HPC). Because HPC is currently dominated by many-core architectures ...
Comments