Zobrazeno 1 - 10
of 18
pro vyhledávání: '"King, Valerie"'
Autor:
Chakraborty, Trisha, Islam, Abir, King, Valerie, Rayborn, Daniel, Saia, Jared, Young, Maxwell
To defend against denial-of-service (DoS) attacks, we employ a technique called resource burning (RB). RB is the verifiable expenditure of a resource, such as computational power, required from clients before receiving service from the server. To the
Externí odkaz:
http://arxiv.org/abs/2205.08287
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 {\it geometric communication network} where the nodes also occupy points
Externí odkaz:
http://arxiv.org/abs/2104.13499
Each vertex of an arbitrary simple graph on $n$ vertices chooses $k$ random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is $O
Externí odkaz:
http://arxiv.org/abs/1909.11147
Autor:
Mashreghi, Ali, King, Valerie
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 communication cost. x The first work to succeed in computing a spanning tr
Externí odkaz:
http://arxiv.org/abs/1907.12152
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 established research in scalable Byzantine agreement to a more practical mo
Externí odkaz:
http://arxiv.org/abs/1907.10308
Autor:
King, Valerie, Saia, Jared
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 consider the adversary's ability to decide the number of fair coinflips i
Externí odkaz:
http://arxiv.org/abs/1812.10169
Autor:
Mashreghi, Ali, King, Valerie
We provide the first asynchronous distributed algorithms to compute broadcast and minimum spanning tree with $o(m)$ bits of communication, in a graph with $n$ nodes and $m$ edges. For decades, it was believed that $\Omega(m)$ bits of communication ar
Externí odkaz:
http://arxiv.org/abs/1806.04328
We present a deterministic distributed algorithm to compute all-pairs shortest paths(APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in $\tilde{O}(n^{3/2})$ rounds in the Congest model, where $n$ is the number of nodes in t
Externí odkaz:
http://arxiv.org/abs/1804.05441
In the CONGEST model, a communications network is an undirected graph whose $n$ nodes are processors and whose $m$ edges are the communications links between processors. At any given time step, a message of size $O(\log n)$ may be sent by each node t
Externí odkaz:
http://arxiv.org/abs/1502.03320
Autor:
Censor-Hillel, Keren, King, Valerie
Publikováno v:
EPTCS 132, 2013
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 communication, computation and mobility constantly poses new challenges
Externí odkaz:
http://arxiv.org/abs/1310.4595