| 1. |
- Acemoglu, Daron, et al.
(author)
-
Harmonic influence in largescale networks
- 2014. - 3
-
In: ACM SIGMETRICS Performance Evaluation Review. - : Association for Computing Machinery (ACM). - 0163-5999. - 9781450327893 ; 42, s. 24-24
-
Conference paper (peer-reviewed)
|
|
| 2. |
- Altman, Eitan, et al.
(author)
-
Mining Competition in a Multi-Cryptocurrency Ecosystem at the Network Edge: A Congestion Game Approach
- 2019
-
In: Performance Evaluation Review. - : Association for Computing Machinery (ACM). - 0163-5999. ; 46:3, s. 114-117
-
Journal article (peer-reviewed)abstract
- We model the competition over several blockchains characterizing multiple cryptocurrencies as a non-cooperative game. Then, we specialize our results to two instances of the general game, showing properties of the Nash equilibrium. In particular, leveraging results about congestion games, we establish the existence of pure Nash equilibria and provide efficient algorithms for finding such equilibria.
|
|
| 3. |
- Berg, Erik, et al.
(author)
-
Fast Data-Locality Profiling of Native Execution
- 2005
-
In: ACM SIGMETRICS Performance Evaluation Review. - : Association for Computing Machinery (ACM). - 0163-5999. ; 33:1, s. 169-180
-
Journal article (peer-reviewed)abstract
- Performance tools based on hardware counters can efficiently profile the cache behavior of an application and help software developers improve its cache utilization. Simulator-based tools can potentially provide more insights and flexibility and model many different cache configurations, but have the drawback of large run-time overhead.We present StatCache, a performance tool based on a statistical cache model. It has a small run-time overhead while providing much of the flexibility of simulator-based tools. A monitor process running in the background collects sparse memory access statistics about the analyzed application running natively on a host computer. Generic locality information is derived and presented in a code-centric and/or data-centric view.We evaluate the accuracy and performance of the tool using ten SPEC CPU2000 benchmarks. We also exemplify how the flexibility of the tool can be used to better understand the characteristics of cache-related performance problems.
|
|
| 4. |
|
|
| 5. |
- Chalermsook, Parinya, et al.
(author)
-
Social Network Monetization via Sponsored Viral Marketing
- 2015
-
In: SIGMETRICS '15 Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. - : ACM Digital Library. ; , s. 259-270
-
Conference paper (peer-reviewed)abstract
- Viral marketing is a powerful tool for online advertising and sales because it exploits the influence people have on one another. While this marketing technique has been beneficial for advertisers, it has not been shown how the social network providers such as Facebook and Twitter can benefit from it. In this paper, we initiate the study of sponsored viral marketing where a social network provider that has complete knowledge of its network is hired by several advertisers to provide viral marketing. Each advertiser has its own advertising budget and a fixed amount they are willing to pay for each user that adopts their product or shares their ads. The goal of the social network provider is to gain the most revenue from the advertisers. Since the products or ads from different advertisers may compete with each other in getting users' attention, and advertisers pay differently per share and have different budgets, it is very important that the social network providers start the "seeds" of the viral marketing of each product at the right places in order to gain the most benefit.We study both when advertisers have limited and unlimited budgets. In the unlimited budget setting, we give a tight approximation algorithm for the above task: we present apolynomial-time O (log n)-approximation algorithm for max-imizing the expected revenue, where n is the number of nodes (i.e., users) in the social network, and show that nopolynomial-time O (log1-εn)-approximation algorithm ex-ists, unlessNPDTIME(n poly log n). In the limited budget setting, we show that it is hopeless to solve the problem(even approximately): unless P=NP, there is no polynomial-time O(n1-ε)-approximation algorithm. We perform exper-iments on several data sets to compare our provable algo-rithms to several heuristic baselines.
|
|
| 6. |
- Chiesa, Marco, et al.
(author)
-
Network Monitoring on Multi-Pipe Switches
- 2023
-
In: Performance Evaluation Review. - : Association for Computing Machinery (ACM). - 0163-5999 .- 1557-9484. ; 51:1, s. 49-50
-
Journal article (peer-reviewed)abstract
- Programmable switches have been widely used to design network monitoring solutions that operate in the fast data-plane level, e.g., detecting heavy hitters, super-spreaders, computing flow size distributions and their entropy. Existing works assume packets access the same memory region in a switch. However, high-speed ASIC switches deploy multiple packet processing pipes, each equipped with its own independent memory. In this work, we first quantify the accuracy degradation due to splitting a monitoring data structure across multiple pipes (e.g., up to 3000x worse flow-size estimation average error). We then present PipeCache, a system that adapts existing data-plane mechanisms to multi-pipe switches by storing monitoring information for a traffic class into a single pipe. PipeCache stores monitoring information into a cache and piggybacks this information onto existing data packets to the correct pipe. Our implementation shows a 2-20x memory reduction to achieve an accuracy similar to single-pipe deployments.
|
|
| 7. |
|
|
| 8. |
- Cho, Jeong-woo, 1978-, et al.
(author)
-
On the Validity of the Fixed Point Equation and Decoupling Assumption for Analyzing the 802.11 MAC Protocol
- 2010
-
In: Performance Evaluation Review. - : Association for Computing Machinery (ACM). - 0163-5999 .- 1557-9484. ; 38:2, s. 36-38
-
Journal article (peer-reviewed)abstract
- Performance evaluation of the 802.11 MAC protocol is classically based on the decoupling assumption, which hypothesizes that the backoff processes at different nodes are independent. A necessary condition for the validity of this approach is the existence and uniqueness of a solution to a fixed point equation. However, it was also recently pointed out that this condition is not sufficient; in contrast, a necessary and sufficient condition is a global stability property of the associated ordinary differential equation. Such a property was established only for a specific case, namely for a homogeneous system (all nodes have the same parameters) and when the number of backoff stages is either 1 or infinite and with other restrictive conditions. In this paper, we give a simple condition that establishes the validity of the decoupling assumption for the homogeneous case. We also discuss the heterogeneous and the differentiated service cases and show that the uniqueness condition is not sufficient; we exhibit one case where the fixed point equation has a unique solution but the decoupling assumption is not valid
|
|
| 9. |
- Combes, R., et al.
(author)
-
Learning to rank : Regret lower bounds and efficient algorithms
- 2015
-
In: Performance Evaluation Review. - : ACM Press. - 0163-5999 .- 1557-9484. ; 43:1, s. 231-244
-
Journal article (peer-reviewed)abstract
- Algorithms for learning to rank Web documents, display ads, or other types of items constitute a fundamental component of search engines and more generally of online services. In such systems, when a user makes a request or visits a web page, an ordered list of items (e.g. documents or ads) is displayed; the user scans this list in order, and clicks on the first relevant item if any. When the user clicks on an item, the reward collected by the system typically decreases with the position of the item in the displayed list. The main challenge in the design of sequential list selection algorithms stems from the fact that the probabilities with which the user clicks on the various items are unknown and need to be learned. We formulate the design of such algorithms as a stochastic bandit optimization problem. This problem differs from the classical bandit framework: (1) the type of feedback received by the system depends on the actual relevance of the various items in the displayed list (if the user clicks on the last item, we know that none of the previous items in the list are relevant); (2) there are inherent correlations between the average relevance of the items (e.g. the user may be interested in a specific topic only). We assume that items are categorized according to their topic and that users are clustered, so that users of the same cluster are interested in the same topic. We investigate several scenarios depending on the available sideinformation on the user before selecting the displayed list: (a) we first treat the case where the topic the user is interested in is known when she places a request; (b) we then study the case where the user cluster is known but the mapping between user clusters and topics is unknown. For both scenarios, we derive regret lower bounds and devise algorithms that approach these fundamental limits.
|
|
| 10. |
- Combes, R., et al.
(author)
-
Unimodal Bandits with Continuous Arms : Order-optimal Regret without Smoothness
- 2020
-
In: Performance Evaluation Review. - : Association for Computing Machinery (ACM). - 0163-5999 .- 1557-9484. ; 48:1, s. 107-108
-
Journal article (peer-reviewed)abstract
- We consider stochastic bandit problems with a continuous set of arms and where the expected reward is a continuous and unimodal function of the arm. For these problems, we propose the Stochastic Polychotomy (SP) algorithms, and derive finite-time upper bounds on their regret and optimization error. We show that, for a class of reward functions, the SP algorithm achieves a regret and an optimization error with optimal scalings, i.e., O( g T ) and O(1/ g T ) (up to a logarithmic factor), respectively.
|
|
