46 citations · 67 across the 18 of their papers we have counts for
9 papers · 1 filter
Communication Costs in a Geometric Communication Network
Sima Hajiaghaei Shanjani, Valerie King
A communication network is a graph in which each node has only local information about the graph and nodes communicate by passing messages along its edges. Here, we consider the {\…
Faster asynchronous MST and low diameter tree construction with sublinear communication
Ali Mashreghi, Valerie King
Building a spanning tree, minimum spanning tree (MST), and BFS tree in a distributed network are fundamental problems which are still not fully understood in terms of time and comm…
Scalable and Secure Computation Among Strangers: Resource-Competitive Byzantine Protocols
John Augustine, Valerie King, Anisur R. Molla +2
Motivated, in part, by the rise of permissionless systems such as Bitcoin where arbitrary nodes (whose identities are not known apriori) can join and leave at will, we extend estab…
Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016
Valerie King, Jared Saia
This is a correction by the authors to "Byzantine Agreement in Expected Polynomial Time" which appeared in the Journal of the ACM in 2016. It corrects a failure in the paper to con…
Broadcast and minimum spanning tree with messages in the asynchronous CONGEST model
Ali Mashreghi, Valerie King
We provide the first asynchronous distributed algorithms to compute broadcast and minimum spanning tree with bits of communication, in a graph with nodes and edges.…
Construction and impromptu repair of an MST in a distributed network with o(m) communication
Valerie King, Shay Kutten, Mikkel Thorup
In the CONGEST model, a communications network is an undirected graph whose nodes are processors and whose edges are the communications links between processors. At any giv…
Proceedings Ninth International Workshop on Foundations of Mobile Computing
Keren Censor-Hillel, Valerie King
Mobile communication has become a vigorous field of research in computer science, due to the wide spreading of mobile technologies, applications and services. The intertwining of c…
A Resource-Competitive Jamming Defense
Valerie King, Seth Pettie, Jared Saia +1
Consider a scenario where Alice wishes to send a message to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmiss…
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
Valerie King, Jared Saia
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only bits, where is the total number of processor…