Testing Equality Under the Local Broadcast Model
Testing Equality Under the Local Broadcast Model
复制标题
检验本地广播模式下的平等性
DOI：
10.1007/978-3-030-79527-6_15
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Khan M.S., Vaidya N.H.
中科院分区：
文献类型：
--
作者：
Khan M.S., Vaidya N.H.
In themultiparty equality problem, each of thennodes starts with ak-bit input. If there is a mismatch between the inputs, thenat least onenode must be able to detect it. The cost of a multiparty equality protocol is the total number of bits sent in the protocol. We consider the problem of minimizing this communication cost under thelocal broadcastmodel for the case where the underlying communication graph is undirected. In thelocal broadcastmodel of communication, a message sent by a node is received identically by all of its neighbors. This is in contrast to the classicalpoint-to-pointcommunication model, where a message sent by a node to one of its neighbors is received only by its intended recipient.Under point-to-point communication, there exists a simple protocol which is competitive within a factor 2 of the lower bound . In this protocol, a rooted spanning tree is fixed and each node sends its entire input to its parent in the tree. On receiving a value from its child, a node compares it against its own input to check if the two values match. Ignoring lower order additive terms, a more complicated protocol comes within a factorof the lower bound and is tight for certain classes of graphs . Tight results, ignoring lower order terms, are also known for complete graphs [, ].We study the multiparty equality problem under the local broadcast model. Recently, our work has shown that the connectivity requirements for Byzantine consensus are lower in the local broadcast model as compared to the classical model [, ]. In this work,we identify a lower bound for the multiparty equality problem in this model.we first identify simple protocols, wherein nodes are restricted to either transmit their entire input or not transmit anything at all, and find that these can costtimes the lower bound using existing example for the set cover problem .we then design a protocol to solve the problem within a constant factor of the lower bound.
DOI：
--
发表时间：
2010
期刊：
Colloquium on Structural Information & Communication Complexity
影响因子：
--
作者：
Guanfeng Liang;N. Vaidya
通讯作者：
N. Vaidya
测试通信图中的相等性
影响因子：
2.5
作者：
N. Alon;K. Efremenko;B. Sudakov
通讯作者：
B. Sudakov
DOI：
10.1007/978-3-662-47666-6_43
发表时间：
2015
期刊：
XRDS
影响因子：
--
作者：
A. Chattopadhyay;A. Rudra
通讯作者：
A. Rudra