1,721,016 research outputs found
On Pareto Optimality in Social Distance Games
No full textWe investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already consid- ered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable un- der the deviation of the grand coalition, as they do not per- mit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximiz- ing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ,√n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combina- tions: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges
A Big Data analyzer for large trace logs
Full text linkCurrent generation of Internet-based services are typically hosted on large data centers that take the form of warehouse-size structures housing tens of thousands of servers. Continued availability of a modern data center is the result of a complex orchestration among many internal and external actors including computing hardware, multiple layers of intricate software, networking and storage devices, electrical power and cooling plants. During the course of their operation, many of these components produce large amounts of data in the form of event and error logs that are essential not only for identifying and resolving problems but also for improving data center efficiency and management. Most of these activities would benefit significantly from data analytics techniques to exploit hidden statistical patterns and correlations that may be present in the data. The sheer volume of data to be analyzed makes uncovering these correlations and patterns a challenging task. This paper presents Big Data analyzer (BiDAl), a prototype Java tool for log-data analysis that incorporates several Big Data technologies in order to simplify the task of extracting information from data traces produced by large clusters and server farms. BiDAl provides the user with several analysis languages (SQL, R and Hadoop MapReduce) and storage backends (HDFS and SQLite) that can be freely mixed and matched so that a custom tool for a specific task can be easily constructed. BiDAl has a modular architecture so that it can be extended with other backends and analysis languages in the future. In this paper we present the design of BiDAl and describe our experience using it to analyze publicly-available traces from Google data clusters, with the goal of building a realistic model of a complex data center
Nash Stability in Social Distance Games
No full textWe consider Social Distance Games (SDGs), that is cluster formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. We adopt Nash stable outcomes, that is states in which no agent can im- prove her utility by unilaterally changing her coalition, as the target solution concept. Although SDGs always admit a Nash equilibrium, we prove that it is NP-hard to find a social wel- fare maximizing one and obtain a negative result concerning the game convergence. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the num- ber of nodes of the underlying graph, and a lower bound on the price of stability of 6/5 − ε. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5
A Big Data Analyzer for Large Trace Logs
No full textCurrent generation of Internet-based services are typically hosted on large data centers that take the form of warehouse-size structures hous-ing tens of thousands of servers. Continued availability of a modern data center is the result of a complex orchestration among many internal and external actors including computing hardware, multiple layers of intricate software, networking and storage devices, electrical power and cooling plants. During the course of their operation, many of these components produce large amounts of data in the form of event and error logs that are essential not only for identifying and resolving problems but also for improving data center efficiency and management. Most of these activi-ties would benefit significantly from data analytics techniques to exploit hidden statistical patterns and correlations that may be present in the data. The sheer volume of data to be analyzed makes uncovering these correlations and patterns a challenging task. This paper presents BiDAl, a prototype Java tool for log-data analysis that incorporates several Big Data technologies in order to simplify the task of extracting information from data traces produced by large clusters and server farms. BiDAl provides the user with several analysis languages (SQL, R and Hadoop MapReduce) and storage backends (HDFS and SQLite) that can be freely mixed and matched so that a custom tool for a specific task can be easily constructed. BiDAl has a modular architecture so that it can be extended with other backends and analysis languages in the future. In this paper we present the design of BiDAl and describe our experience using it to analyze publicly-available traces from Google data clusters, with the goal of building a realistic model of a complex data center.
Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols
No full textWe study leader election problem via ranking within self-stabilising population protocols. In this scenario, the agent's state space comprises n rank states and x extra states. The initial configuration of n agents consists of arbitrary arrangements of rank and extra states, with the objective of self-ranking. Specifically, each agent is tasked with stabilising in a unique rank state silently, implying that after stabilisation, each agent remains in its designated state indefinitely.The ranking problem is a pivotal challenge in self-stabilising population protocols, with its resolution resulting in leader election and requiring a minimum of n states [23]. Within this framework, a self-stabilising ranking protocol is deemed state-optimal if it exclusively employs rank states. It is assumed to be near-state optimal if it incorporates O (log n) extra states, denoted as x = O (log n). Additionally, a configuration of agents' states is referred to as k-distant (from the final configuration) if exactly k rank states are not used in the initial setup.A generic state-optimal ranking population protocol AG demonstrates silent self-stabilisation within a time frame of ⊙(n2) with high probability (whp). It is established in [22, 30] that any self-stabilising silent leader election protocol demands ω(n) expected time. Furthermore, [22] introduces silent ranking protocols with expected times of both O(n) and O(n log n) whp, each utilising x = ω (n) extra states, recently improved to x = O (log2 n) extra states in [16]. However, the exact complexity of near-state and state-optimal self-stabilising ranking remains elusive. Particularly, questions whether state-optimal self-stabilising ranking is viable in time o(n2) whp, and the exploration of the trade-off between the number of extra states and stabilisation time, remain unanswered.We present several new self-stabilising ranking (and in turn leader election) protocols, greatly enriching our comprehension of these intricate problems. All protocols ensure self-stabilisation time with high probability (whp). We delve into three scenarios, from which we derive stable (always correct), either state-optimal or nearly state-optimal, silent ranking protocols that self-stabilise within a time frame of o(n2) whp, including:(1) In Section 3, we show that a novel concept of an agent trap admits a state-optimal ranking self-stabilising in time O(min(kn3/2, n2 log2 n)), for any k-distant starting configuration.(2) We also show that one extra state (x = 1) enables a ranking protocol that self-stabilises in time O(n7/4 log2 n) = o(n2), regardless of the initial configuration, see Section 4.(3) Finally, in Section 5, we show that extra x = O (log n) states admit self-stabilising ranking with the best currently known time O(n log n), with whp and silent guarantees imposed
PODC 2020 live recording, session: graph algorithms and congest model
No full text<p>A recording of the "graph algorithms and congest model" session in PODC 2020. This session took place on Thursday, 6-Aug-2020, and was chaired by Alkida Balliu.</p>
Software per l'analisi di Big Data su più livelli e sua applicazione a tracce di Google
Full text linkCon l'avanzare della tecnologia, i Big Data hanno assunto un ruolo importante.
In questo lavoro è stato implementato, in linguaggio Java, un software volto alla analisi dei Big Data mediante R e Hadoop/MapReduce. Il software è stato utilizzato per analizzare le tracce rilasciate da Google, riguardanti il funzionamento dei suoi data center
Learning Hierarchically-Structured Concepts II: Overlapping Concepts, and Networks With Feedback
Full text linkWe continue our study from Lynch and Mallmann-Trenn (Neural Networks, 2021), of how concepts that have hierarchical structure might be represented in brain-like neural networks, how these representations might be used to recognize the concepts, and how these representations might be learned. In Lynch and Mallmann-Trenn (Neural Networks, 2021), we considered simple tree-structured concepts and feed-forward layered networks. Here we extend the model in two ways: we allow limited overlap between children of different concepts, and we allow networks to include feedback edges. For these more general cases, we describe and analyze algorithms for recognition and algorithms for learning
- …
