BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Jared Saia

Jared Saia contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingComputer Science and Game Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2020arXiv

Resource Burning for Permissionless Systems

Proof-of-work puzzles and CAPTCHAS consume enormous amounts of energy and time. These techniques are examples of resource burning: verifiable consumption of resources solely to convey information. Can these costs be eliminated? It seems unlikely since resource burning shares similarities with "money burning" and "costly signaling", which are foundational to game theory, biology, and economics. Can these costs be reduced? Yes, research shows we can significantly lower the asymptotic costs of resource burning in many different settings. In this paper, we survey the literature on resource burning; take positions based on predictions of how the tool is likely to evolve; and propose several open problems targeted at the theoretical distributed-computing research community.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

ToGCom: An Asymmetric Sybil Defense

Proof-of-work (PoW) is one of the most common techniques to defend against Sybil attacks. Unfortunately, current PoW defenses have two main drawbacks. First, they require work to be done even in the absence of an attack. Second, during an attack, they require good identities (IDs) to spend as much as the attacker. Recent theoretical work by Gupta, Saia, and Young suggests the possibility of overcoming these two drawbacks. In particular, they describe a new algorithm, GMCom, that always ensures that a minority of IDs are Sybil. They show that rate at which all good IDs perform computation is $O(J_G + \sqrt{T(J_G+1)})$, where $J_G$ is the join rate of good IDs, and $T$ is the rate at which the adversary performs computation. Unfortunately, this cost bound only holds in the case where (1) GMCom always knows the join rate of good IDs; and (2) there is a fixed constant amount of time that separates join events by good IDs. Here, we present ToGCom, which removes these two shortcomings. To do so, we design and analyze a mechanism for estimating the join rate of good IDs; and also devise a new method for setting the computational cost to join the system. Additionally, we evaluate the performance of ToGCom alongside prior PoW-based defenses. Based on our experiments, we design heuristics that further improve the performance of ToGCom by up to $3$ orders of magnitude over these previous Sybil defenses.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Scalable Mechanisms for Rational Secret Sharing

We consider the classical secret sharing problem in the case where all agents are selfish but rational. In recent work, Kol and Naor show that, when there are two players, in the non-simultaneous communication model, i.e. when rushing is possible, there is no Nash equilibrium that ensures both players learn the secret. However, they describe a mechanism for this problem, for any number of players, that is an epsilon-Nash equilibrium, in that no player can gain more than epsilon utility by deviating from it. Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send O(n) messages in expectation, where n is the number of agents. This may be problematic for some applications of rational secret sharing such as secure multi-party computation and simulation of a mediator. We address this issue by describing mechanisms for rational secret sharing that are designed for large n. Both of our results hold for n > 2, and are Nash equilbria, rather than just epsilon-Nash equilbria. Our first result is a mechanism for n-out-of-n rational secret sharing that is scalable in the sense that it requires each agent to send only an expected O(log n) bits. Moreover, the latency of this mechanism is O(log n) in expectation, compared to O(n) expected latency for the Kol and Naor result. Our second result is a mechanism for a relaxed variant of rational m-out-of-n secret sharing where m = Theta(n). It requires each processor to send O(log n) bits and has O(log n) latency. Both of our mechanisms are non-cryptographic, and are not susceptible to backwards induction.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary

We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only $\tilde{O}(\sqrt{n})$ bits, where $n$ is the total number of processors. Our algorithm succeeds with high probability against an \emph{adaptive adversary}, which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1/3 fraction. We assume synchronous communication but a \emph{rushing} adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in $n$. To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring $o(n^{2})$ total bits of communication.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Combinatorial Auctions with Budgets

We consider budget constrained combinatorial auctions where bidder $i$ has a private value $v_i$, a budget $b_i$, and is interested in all the items in $S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot v_i$. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is known that even of all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality for such auctions when the valuations are private and the budgets are public knowledge. This extends the result of Dobzinski et al. (FOCS 2008) for auctions of multiple {\sl identical} items and public budgets to single-valued {\sl combinatorial} auctions with public budgets.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Improved Approximation Algorithms for Segment Minimization in Intensity Modulated Radiation Therapy

he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes in each row are consecutive. This has direct applications in intensity-modulated radiation therapy, an effective form of cancer treatment. We develop three approximation algorithms for matrices with arbitrarily many rows. Our first two algorithms improve the approximation factor from the previous best of $1+\log_2 h $ to (roughly) $3/2 \cdot (1+\log_3 h)$ and $11/6\cdot(1+\log_4{h})$, respectively, where $h$ is the largest entry in the intensity matrix. We illustrate the limitations of the specific approach used to obtain these two algorithms by proving a lower bound of $\frac{(2b-2)}{b}\cdot\log_b{h} + \frac{1}{b}$ on the approximation guarantee. Our third algorithm improves the approximation factor from $2 \cdot (\log D+1)$ to $24/13 \cdot (\log D+1)$, where $D$ is (roughly) the largest difference between consecutive elements of a row of the intensity matrix. Finally, experimentation with these algorithms shows that they perform well with respect to the optimum and outperform other approximation algorithms on 77% of the 122 test cases we consider, which include both real world and synthetic data.

0 citations0 reviewsNo code linkedOpen access