Computing functions on asynchronous anonymous networks

Masafumi Yamashita, T. Kameda

研究成果: ジャーナルへの寄稿学術誌査読

11 被引用数 (Scopus)


In an "anonymous" network the processors have no identity numbers. We investigate the problem of computing a given function f on an asynchronous anonymous network in the sense that each processor computes f(I) for any input I = (I(ν1),..., I(νn)), where I(νi) is the input to processor νi, i = 1, 2,...,n. We address the following three questions: (1) What functions are computable on a given network? (2) Is there a "universal" algorithm which, given any network G and any function f computable on G as inputs, computes f on G? (3) How can one find lower bounds on the message complexity of computing various functions on anonymous networks? We give a necessary and sufficient condition for a function to be computable on an asynchronous anonymous network, and present a universal algorithm for computing f(I) on any network G, which accepts G and F computable on G, as well as {I(νi)}, as inputs. The universal algorithm requires O(mn) messages in the worst case, where n and m are the numbers of processors and links in the network, respectively. We also propose a method for deriving a lower bound on the number of messages necessary to solve the above problem on asynchronous anonymous networks.

ジャーナルTheory of Computing Systems
出版ステータス出版済み - 1月 1 1996

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • 計算理論と計算数学


「Computing functions on asynchronous anonymous networks」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。