Distributedly Solving Boolean Equations over Networks

被引:0
作者
Qi, Hongsheng [1 ,2 ]
Li, Bo [3 ]
Jing, Rui-Juan [4 ]
Proutiere, Alexandre [5 ]
Shi, Guodong [6 ]
机构
[1] Chinese Acad Sci, Acad Math & Syst Sci, Inst Syst Sci, Key Lab Syst & Control, Beijing, Peoples R China
[2] Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
[3] Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Math Mechanizat, Beijing, Peoples R China
[4] Jiangsu Univ, Fac Sci, Zhenjiang 212013, Jiangsu, Peoples R China
[5] KTH Royal Inst Technol, Dept Automat Control, S-10044 Stockholm, Sweden
[6] Univ Sydney, Australian Ctr Field Robot, Sch Aerosp Mech & Mechatron Engn, Sydney, NSW, Australia
来源
2020 59TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC) | 2020年
基金
澳大利亚研究理事会;
关键词
Distributed algorithm; Boolean equation; ALGORITHMS; CONSENSUS; OPTIMIZATION; SPREAD;
D O I
10.1109/cdc42340.2020.9304144
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we propose distributed algorithms that solve a system of Boolean equations over a network, where each node in the network possesses only one Boolean equation from the system. The Boolean equation assigned at any particular node is a private equation known to this node only, and the nodes aim to compute the exact set of solutions to the system without exchanging their local equations. We show that each private Boolean equation can be locally lifted to a linear algebraic equation under a basis of Boolean vectors, leading to a network linear equation that is distributedly solvable. A number of exact or approximate solutions to the induced linear equation are then computed at each node from different initial values. The solutions to the original Boolean equations are eventually computed locally via a Boolean vector search algorithm. We prove that given solvable Boolean equations, when the initial values of the nodes for the distributed linear equation solving step are i.i.d selected according to a uniform distribution in a high-dimensional cube, our algorithms return the exact solution set of the Boolean equations at each node with high probability.
引用
收藏
页码:560 / 565
页数:6
相关论文
共 33 条
[1]   Positive and negative circuits in discrete neural networks [J].
Aracena, J ;
Demongeot, J ;
Goles, E .
IEEE TRANSACTIONS ON NEURAL NETWORKS, 2004, 15 (01) :77-83
[2]   Fixed points in conjunctive networks and maximal independent sets in graph contractions [J].
Aracena, Julio ;
Richard, Adrien ;
Salinas, Lilian .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 88 :145-163
[3]  
Arora S., 2009, COMPUT COMPLEX
[4]   Convergence of Consensus Models With Stochastic Disturbances [J].
Aysal, Tuncer Can ;
Barner, Kenneth E. .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 57 (08) :4101-4113
[5]   On the complexity of solving quadratic Boolean systems [J].
Bardet, Magali ;
Faugere, Jean-Charles ;
Salvy, Bruno ;
Spaenlehauer, Pierre-Jean .
JOURNAL OF COMPLEXITY, 2013, 29 (01) :53-75
[6]   Projection algorithms for solving convex feasibility problems [J].
Bauschke, HH ;
Borwein, JM .
SIAM REVIEW, 1996, 38 (03) :367-426
[7]   Performance of a Distributed Stochastic Approximation Algorithm [J].
Bianchi, Pascal ;
Fort, Gersende ;
Hachem, Walid .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (11) :7405-7418
[8]   A Linear Representation of Dynamics of Boolean Networks [J].
Cheng, Daizhan ;
Qi, Hongsheng .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2010, 55 (10) :2251-2258
[9]   Controllability and observability of Boolean control networks [J].
Cheng, Daizhan ;
Qi, Hongsheng .
AUTOMATICA, 2009, 45 (07) :1659-1667
[10]  
Cheng DH, 2011, COMMUN CONTROL ENG, P1, DOI 10.1007/978-0-85729-097-7