Multiprocessor scheduling of hard real-time tasks modeled by directed acyclic graphs (DAGs) exploits the inherent parallelism presented by the model. For DAG tasks, a node represents a request to execute an object on one of the available processors. In one DAG task, there may be multiple execution requests for one object, each represented by a distinct node. These distinct execution requests offer an opportunity to reduce their combined cache overhead through coordinated scheduling of objects as threads within a parallel task. The goal of this work is to realize this opportunity by incorporating the cache-aware BUNDLE-scheduling algorithm into federated scheduling of sporadic DAG task sets.This is the first work to incorporate instruction cache sharing into federated scheduling. The result is a modification of the DAG model named the DAG with objects and threads (DAG-OT). Under the DAG-OT model, descriptions of nodes explicitly include their underlying executable object and number of threads. When possible, nodes assigned the same executable object are collapsed into a single node; joining their threads when BUNDLE-scheduled. Compared to the DAG model, the DAG-OT model with cache-aware scheduling reduces the number of cores allocated to individual tasks by approximately 20 percent in the synthetic evaluation and up to 50 percent on a novel parallel computing platform implementation. By reducing the number of allocated cores, the DAG-OT model is able to schedule a subset of previously infeasible task sets.
more »
« less
AOT: Anonymization by oblivious transfer
We introduce AOT, an anonymous communication system based on mix network architecture that uses oblivious transfer (OT) to deliver messages.
Using OT to deliver messages helps AOT resist blending (n-1) attacks and
helps AOT preserve receiver anonymity, even if a covert adversary controls all nodes in AOT.
AOT comprises three levels of nodes, where nodes at each level perform a different function and can scale horizontally. The sender encrypts their payload and a tag---derived from a secret shared between the sender and receiver---with the public key of a Level-2 node and sends them to a Level-1 node. On a public bulletin board, Level-3 nodes publish tags associated with messages ready to be retrieved.
Each receiver checks the bulletin board, identifies tags, and receives the associated messages using OT.
A receiver can receive their messages even if the receiver is offline when messages are ready.
Through what we call a ``handshake'' process, communicants can use the AOT protocol to establish shared secrets anonymously.
Users play an active role in contributing to the unlinkability of messages:
periodically, users initiate requests to AOT to receive dummy messages,
such that an adversary cannot distinguish real and dummy requests.
more »
« less
- Award ID(s):
- 1753681
- NSF-PAR ID:
- 10290934
- Date Published:
- Journal Name:
- Privacy Enhanced Tecologies, submtted
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The Bitcoin blockchain scalability problem has inspired several offchain solutions for enabling cryptocurrency transactions, of which Layer-2 systems such as payment channel networks (PCNs) have emerged as a frontrunner. PCNs allow for path-based transactions between users without the need to access the blockchain. These path-based transactions are possible only if a suitable path exists from the sender of a payment to the receiver. In this paper, we propose Auroch, a distributed auction-based pathfinding and routing protocol that takes into account the routing fees charged by nodes along a path. Unlike other routing protocols proposed for PCNs, Auroch takes routing fees into consideration. Auroch maximizes the profit that can be achieved by an intermediate node at the same time minimizing the overall payment cost for the sender.more » « less
-
more » « less
Abstract Communication networks have multiple users, each sending and receiving messages. A multiple access channel (MAC) models multiple senders transmitting to a single receiver, such as the uplink from many mobile phones to a single base station. The optimal performance of a MAC is quantified by a capacity region of simultaneously achievable communication rates. We study the two-sender classical MAC, the simplest and best-understood network, and find a surprising richness in both a classical and quantum context. First, we find that quantum entanglement shared between senders can substantially boost the capacity of a classical MAC. Second, we find that optimal performance of a MAC with bounded-size inputs may require unbounded amounts of entanglement. Third, determining whether a perfect communication rate is achievable using finite-dimensional entanglement is undecidable. Finally, we show that evaluating the capacity region of a two-sender classical MAC is in fact NP-hard.
-
In wireless networked control systems, ensuring predictable communication link reliabilities among sensors, controllers, and actuators is critical. In such scenarios, different data gathered at the application layer of each sender require different packet delivery ratios (i.e., reliabilities). The lower layers try to accommodate these requests by first mapping each of them into a service level and then deliver the associated data packets to the receiver at the mapped service level. Due to resource constraints and maintenance overhead, the number of supported service levels is usually limited. An important question is then how to determine the set of service levels to maintain and how to map each request to an appropriate service level, such that the requested reliabilities are guaranteed and the total cost of mapping is minimized? We formally formulate this as an optimal request clustering problem since each service level acts as a cluster and can host multiple requests. In particular, we formulate the Migratory Clustering Problem and the Non-Migratory Clustering Problem, depending on whether a request can migrate from one service level to another after its initial assignment. We propose two optimal algorithms to solve both problems.more » « less
-
Nissim, K. ; Waters, B. (Ed.)Recent new constructions of rate-1 OT [Döttling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender's input size) number of group elements for a single instance of rate-1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver. In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs. - PIR: We obtain a rate-1 PIR scheme with client communication cost of $O(\lambda\cdot\log N)$ group elements for security parameter $\lambda$ and database size $N$. Notably, after a one-time setup (or one PIR instance), any following PIR instance only requires communication cost $O(\log N)$ number of group elements. - PSI with unbalanced inputs: We apply our techniques to private set intersection with unbalanced set sizes (where the receiver has a smaller set) and achieve receiver communication of $O((m+\lambda) \log N)$ group elements where $m, N$ are the sizes of the receiver and sender sets, respectively. Similarly, after a one-time setup (or one PSI instance), any following PSI instance only requires communication cost $O(m \cdot \log N)$ number of group elements. All previous sublinear-communication non-FHE based PSI protocols for the above unbalanced setting were also based on rate-1 OT, but incurred at least $O(\lambda^2 m \log N)$ group elements.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
