Brief announcement: new bounds for the controller problem

ABSTRACT

The (M, W)-controller, originally studied by Afek, Awerbuch, Plotkin, and Saks, is a basic distributed tool that provides an abstraction for managing the consumption of a global resource in a distributed dynamic network. We establish new bounds on the message complexity of this tool based on a surprising connection between the controller problem and the monotonic labeling problem.

REFERENCES

• 1: Yehuda Afek , Baruch Awerbuch , Serge Plotkin , Michael Saks, Local management of a global resource in a communication network, Journal of the ACM (JACM), v.43 n.1, p.1-19, Jan. 1996 [doi>10.1145/227595.227596]
• 2: Yehuda Afek , Moty Ricklin, Sparser: a paradigm for running distributed algorithms, Journal of Algorithms, v.14 n.2, p.316-328, March 1993 [doi>10.1006/jagm.1993.1016]
• 3: Arne Andersson , Tony W. Lai, Fast Updating of Well-Balanced Trees, Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, p.111-121, July 11-14, 1990
• 4: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton , Jack Zito, Two Simplified Algorithms for Maintaining Order in a List, Proceedings of the 10th Annual European Symposium on Algorithms, p.152-164, September 17-21, 2002
• 5: Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
• 6: Paul F. Dietz , Joel I. Seiferas , Ju Zhang, A Tight Lower Bound for Online Monotonic List Labeling, SIAM Journal on Discrete Mathematics, v.18 n.3, p.626-637, 2005 [doi>10.1137/S0895480100315808]
• 7: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 8: Paul F. Dietz , Ju Zhang, Lower Bounds for Monotonic List Labeling, Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, p.173-180, July 11-14, 1990
• 9: Alon Itai , Alan G. Konheim , Michael Rodeh, A Sparse Table Implementation of Priority Queues, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.417-431, July 13-17, 1981
• 10: Amos Korman , Shay Kutten, Controller and estimator for dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281127]
• 11: Athanasios K. Tsakalidis, Maintaining order in a generalized linked list, Acta Informatica, v.21 n.1, p.101-112, May 1984 [doi>10.1007/BF00289142]
• 12: Dan E. Willard, Maintaining dense sequential files in a dynamic environment (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.114-121, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802183]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms

Keywords:
controller, dynamic networks