We introduce a new model of computation: the online LOCAL model (OLOCAL). In this model, the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node the algorithm can also inspect its radius-$T$ neighborhood before choosing the output; instead of looking ahead in time, we have the power of looking around in space. It is natural to compare OLOCAL with the LOCAL model of distributed computing, in which all nodes make decisions simultaneously in parallel based on their radius-$T$ neighborhoods.
翻译：我们引入了一种新的计算模式:在线LOCAL模型(OLOCAL ) 。 在这个模型中,对手逐个展示输入图的节点,这与经典在线算法一样。 但是,对于每一个新节点,算法也可以在选择输出之前检查其半径-$T$邻里;我们没有时间向前看,而是有在空间周围观察的力量。将OLOCOL与LOCAL分布式计算模型进行比较是自然的,在模型中,所有节点根据半径-$T$邻里的情况同时作出决定。
相关内容
微信扫码咨询专知VIP会员