In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most$D$ones, where$D$is a given input parameter. We provide an$O\left(n^{2} D\right)$-time complexity algorithm for the construction of such codes, where$n$is the number of codewords. We also describe several scenarios where the need to design these kinds of codes naturally arises. Our algorithms allow us to construct both optimal average-length prefix binary codes and optimal average-length alphabetic binary codes. In the former case, our$O\left(n^{2} D\right)$-time algorithm substantially improves on the previously known$O\left(n^{2+D}\right)$-time complexity algorithm for the same problem. We also provide a Kraft-like inequality for the existence of (optimal) variable-length binary codes, subject to the above-described constraint on the number of 1's in each codeword.

By 2030, the World Health Organization estimates that over 2.5 billion people will need assistive technologies, yet nearly one billion will lack access, posing significant barriers to inclusion. While often considered non-essential, creative technologies, particularly in music, have demonstrated therapeutic value and support cognitive well-being. However, physical and cognitive barriers continue to restrict access to active music-making.This work addresses the challenge of democratizing musical creativity by designing Digital Musical Interfaces (DMIs) that are inclusive, adaptable, and capable of supporting both per-formative and therapeutic goals. We propose a comprehensive design framework centered on accessibility, usability, and creative freedom. A key case study illustrates this framework through the development of a gesture-based music system, enabling users to create music solely through hand movements. The framework emerged through a structured series of technological milestones, incorporating AI, IoT, Virtual (VR), and Augmented Reality (AR). Each stage introduced and evaluated specific innovation, such as deep reinforcement learning for gesture recognition, low-latency VR/AR environments, multiplayer interaction, and integration with a full-featured digital audio workstation—via experimental prototypes and iterative user testing.Results of a user evaluation involving educators, musicians, and users, indicate that this interdisciplinary and user-centered approach effectively supports motor-impaired users while remaining accessible and engaging for broader populations.

In this paper we consider evolving 2-threshold secret sharing schemes. In such schemes, the number of participants grows over time and is potentially unbounded, any two participants reconstruct the secret, and no single participant can figure out any partial information about it. They are referred to as$(2,\infty)$-threshold secret sharing schemes. The cost of a$(2,\infty)$-threshold secret sharing scheme can be measured as the maximum, over all possible$n\ge 2$, of the ratio between the sum of the lengths of the shares for the first n participants and the sum of the lengths of the shares for a (standard) optimal$(2,n)$-threshold secret sharing scheme. It is known that such a cost measure is lower bounded by$3/2$. Moreover, currently, the best known$(2,\infty)$-threshold secret sharing scheme has cost 1.59375. Our contribution improves the state-of-the-art in several ways:•We describe a new$(2,\infty)$-threshold secret sharing scheme whose cost is 1.5859375, improving on the previous best known scheme. • Motivated by the fact that in some applications one knows a lower bound on the number of participants, we generalize the cost measure, by considering the maximum over all possible$n\ge z_{0}$, where$z_{0}$is any integer greater than or equal to 2. • We provide constructions of optimal schemes for the generalized cost measure and through a theoretical analysis we prove some interesting properties for the lower bound of the cost. • By using algorithmic techniques, for reasonably small cases, we exhaustively study the problem of finding tight lower bounds. In particular, we obtain a lower bound of 1.534375, improving the lower bound of$3/2$. We close the paper summarizing our findings and discussing some open issues.

The design of digital musical instruments is based on the perceptions, especially visual, that they can generate in users during their use. Given the multifaceted nature of musical expression, this aspect plays a crucial role in shaping their playability, requiring careful selection of the information to integrate into the instrument's interface. In this context, the music visualization techniques can offer substantial assistance, aiding in the pedagogical process of mastering these tools. In this work, we introduce Pulsate, an Android application engineered to enable real-time music composition by leveraging visual perceptions generated through the collision dynamics of geometric shapes resulting from the user's tactile interactions at specific points on the screen. The development of Pulsate involved the integration of various features: (i) provision for polytonality and different musical scales, (ii) internal playback modes which include percussive, harmonic, and melodic functionalities, (iii) incorporation of the MIDI protocol to facilitate control over external instruments. Through these features, Pulsate offers an intuitive platform for real-time music production. To realize this objective, we capitalized on graphics-oriented programming language processing capabilities. An evaluation study was conducted to assess the efficacy of how music can be produced expressively, involving a heterogeneous cohort of participants with varied musical backgrounds and degrees of proficiency in music theory. A further usability study was conducted to analyze the overall user satisfaction. The results of these studies provided us with positive feedback regarding the effectiveness of the concept, the aesthetic appeal of the graphical interface, and user satisfaction concerning the usability and utility of the provided tool.

Distributed Secret Sharing is a (multi) secret sharing model in which the shares are distributed over storage nodes of a network and each participant is able to reconstruct a specific secret by accessing a subset of the storage nodes. In this work, we provide new Distributed (multi) Secret Sharing Protocols for a specific class of access structures, namely those that can be described with a graph. The protocols improve on previous results allowing a faster encoding and decoding phase while maintaining optimal storage requirements. Moreover, our protocols can manage any kind of graph, while previous protocols have been designed only for complete graphs, and we provide a complete characterization of graph-based protocols. We also prove some tight bounds on the size of the information held in the storage nodes and communication complexity by using an information-theoretic approach. Finally, we also introduce a computationally secure technique for the general case that allows improvements in the size of the needed disk space if secrecy is computational, that is, if the scheme is robust against resource-bounded adversaries.

Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.

We define and implement a novel side-channel attack that exploits a smartphone’s accelerometer to eavesdrop entire words that the device itself is reproducing through its loudspeakers. The proposed approach consists of two modules: (i) a deep learning-based system that, using a Convolutional Neural Network (CNN), learns to recognize a set of significant speech units, using the spectrogram representation of the corresponding acceleration signals; (ii) an evolutionary-based segmentation method that, given the accelerometer measurements corresponding to an input speech, finds the best way to split it so that the proposed CNN maintains a high classification performance on each of the segments obtained, guarantying the recognition of a significant percentage of words from the original speech. Results of experiments performed to assess the effectiveness of the proposed attack, show its ability to recognize a percentage of words which is higher for short speeches and diminishes as the speeches get longer. We experimented with speeches of lengths ranging from 5 to 60 s, obtaining a recognition percentage going from about 80% for the shortest speeches, down to about 54% for the longest ones.

In Distributed Secret Sharing schemes, secrets are encoded with shares distributed over multiple nodes of a network. Each involved party has access to a subset of the nodes and thus to a subset of the shares and is able to reconstruct a specific secret. Usually, these schemes are evaluated by measuring the required storage overhead, as well as the encoding and decoding complexities. In this paper, we provide new Distributed (multi) Secret Sharing Protocols for$(k,n)$-threshold access structures that improve on previous results, characterized by nearly-optimal storage overhead, achieving both storage optimality and a better encoding/decoding complexity. The protocols are also simpler than previous ones and allow for easier encoding.

Plagiarism is a debated and controversial topic in different fields. For example, in Law, where the subjectivity of the judges that have to pronounce a suspicious case usually lead to long and often unsolved cases, and in Music, where huge amounts of money are invested every year to face and try to solve suspicious cases. In this scenario, the automatic detection of music plagiarism is fundamental by representing useful support for judges during their pronouncements and an important result to avoid musicians spending more time in court than on composing music. This paper shows how the combination of visual analytics and the employment of adaptive meta-heuristics can assist domain experts in judging suspicious cases. Solutions will be presented as part of PlagiarismDetection, a cross-platform tool that leverages text-similarity algorithms, computational intelligence, optimization methods, and visualization techniques to enable new critical approaches to music plagiarism analysis.

Abstract Plagiarism is a controversial and debated topic in different fields, especially in the Music one, where the commercial market generates a huge amount of money. The lack of objective metrics to decide whether a song is a plagiarism, makes music plagiarism detection a very complex task: often decisions have to be based on subjective argumentations. Automated music analysis methods that identify music similarities can be of help. In this work, we first propose two novel such methods: a text similarity-based method and a clustering-based method. Then, we show how to combine them to get an improved (hybrid) method. The result is a novel adaptive meta-heuristic for music plagiarism detection. To assess the effectiveness of the proposed methods, considered both singularly and in the combined meta-heuristic, we performed tests on a large dataset of ascertained plagiarism and non-plagiarism cases. Results show that the meta-heuristic outperforms existing methods. Finally, we deployed the meta-heuristic into a tool, accessible as a Web application, and assessed the effectiveness, usefulness, and overall user acceptance of the tool by means of a study involving 20 people, divided into two groups, one of which with access to the tool. The study consisted in having people decide which pair of songs, in a predefined set of pairs, should be considered plagiarisms and which not. The study shows that the group supported by our tool successfully identified all plagiarism cases, performing all tasks with no errors. The whole sample agreed about the usefulness of an automatic tool that provides a measure of similarity between two songs.

Abstract Splicing systems are a form of DNA computing as they mimic the recombination process among DNA molecules. This work discusses the use of splicing systems to build automatic tools for reproducing human beings’ creativity, in the context of automatic music composition. More specifically, this work describes three general splicing system approaches for automatic music composition, and their application to two specific cases, namely composing 4-voice music and composing Jazz solos in a given style. Examples of music composed by the systems are presented.

Several works on representation learning for graph-structured data have been proposed in recent literature. However, most of such techniques have several downsides. On the one hand, graph kernels which use handcrafted features (e.g., shortest paths) are hampered by poor generalization problems. On the other hand, methods for learning representations of whole graphs deal with unattributed or single-attributed graphs.In this work, we propose a novel technique for graph embedding learning able to take into account multi-attribute graphs (from 1 to an arbitrary number). Given a multi-attribute graph, the proposed method generates an embedding vector as follows: (i) the graph is split into several single-attribute graphs; for each of these, one numeric vector is generated by using state-of-the-art graph embedding techniques; (ii) the obtained vectors are concatenated in one representative vector using a multi-view learning integration technique; (iii) the size of such a vector is reduced through deep autoencoders.Experiments have been conducted on the music style recognition problem. We focus on the corpus of 4-voice J. S. Bach’ compositions. First, such a corpus has been decomposed and translated into graph-based structures corresponding to the music scores. Then, the proposed method is applied to generate the embedding vectors from the obtained graphs. Finally, a Random Forest model trained on such obtained vectors is used for generating novels music compositions in the learned style. Results obtained show the effectiveness of the proposed approach.

During the traditional music analysis process, stylistic rules usually have to be deduced directly from examples of compositions or past performance. In such cases, musicians create external representations of a music style domain as source for reflection, inspiration and collaboration. However, due to the large number of music examples, creating such representations can be essential, but at the same time, slow and costly.In this paper, we show that interactive visualization and machine learning could aid in supporting and enhancing musician cognition and team-based collaboration. Specifically, we propose an approach to this problem which: (1) allows musicians to visually externalize their evolving mental models of a music domain, in the form of thematically organized anchored pairs. i.e., (narrative, graph), each one corresponding to a specific music pattern, and (2) uses such pairs to develop a music style classification system based on machine learning, as support for musicians during their activities (composition, performance). To this end, we introduce a novel graph representation of music stylistic patterns and discuss the advantages of linking such a representation to machine learning. Results of a preliminary study involving 10 musicians provided us with overall positive feedback about the effectiveness of our approach as well as further directions to explore.

Evolutionary algorithms mimic evolutionary behaviors in order to solve problems. They have been successfully applied in many areas and appear to have a special relationship with creative problems; such a relationship, over the last two decades, has resulted in a long list of applications, including several in the field of music. In this article, we provide an evolutionary algorithm able to compose music. More specifically we consider the following 4-voice harmonization problem: one of the 4 voices (which are bass, tenor, alto, and soprano) is given as input and the composer has to write the other 3 voices in order to have a complete 4-voice piece of music with a 4-note chord for each input note. Solving such a problem means finding appropriate chords to use for each input note and also finding a placement of the notes within each chord so that melodic concerns are addressed. Such a problem is known as the unfigured harmonization problem. The proposed algorithm for the unfigured harmonization problem, named EvoComposer, uses a novel representation of the solutions in terms of chromosomes (that allows to handle both harmonic and nonharmonic tones), specialized operators (that exploit musical information to improve the quality of the produced individuals), and a novel hybrid multiobjective evaluation function (based on an original statistical analysis of a large corpus of Bach's music). Moreover EvoComposer is the first evolutionary algorithm for this specific problem. EvoComposer is a multiobjective evolutionary algorithm, based on the well-known NSGA-II strategy, and takes into consideration two objectives: the harmonic objective, that is finding appropriate chords, and the melodic objective, that is finding appropriate melodic lines. The composing process is totally automatic, without any human intervention. We also provide an evaluation study showing that EvoComposer outperforms other metaheuristics by producing better solutions in terms of both well-known measures of performance, such as hypervolume, [Formula: see text] index, coverage of two sets, and standard measures of music creativity. We conjecture that a similar approach can be useful also for similar musical problems.

In order to master the harmonic analysis of musical compositions, a musician needs to profoundly understand the music theory, have an extensive training, and put a considerable effort in the task. For learners it can be a time-consuming and tedious task due to the steep learning curve. The idea throughout this paper is to visually annotate musical compositions with the objective to support users in performing the harmonic analysis, in which the task is mainly based on the identification of similar tonalities and relevant degrees. The paper proposes two visualisations that use rectangles to represent tonalities and the degree and exploit colours to represent similarities. The design of visualisations is based on guidelines drawn from informal interviews with teachers of the Conservatorio G. Martucci, a conservatory in Salerno, and from literature. The evaluation study by involving 30 participants showed that overall the 30 participants of the evaluation study achieved better results performing the harmonic analysis using the musical composition enhanced with visualisations compared to the standard musical composition; it is a promising result that encourages further investigation in the field.

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

Plagiarism, i.e., copying the work of others and trying to pass it off as one own, is a debated topic in different fields. In particular, in music field, the plagiarism is a controversial and debated phenomenon that has to do with the huge amount of money that music is able to generate. However, the existing mechanisms for plagiarism detection mainly apply superficial and brute-force string matching techniques. Such well-known metrics, widely used to discover similarities in text documents, cannot work well in discovering similarities in music compositions. Despite the wide-spread belief that few notes in common between two songs is enough to decide whether a plagiarism exists, the analysis of similarities is a very complex process. In this work, we provide novel perspectives in the field of automatic music plagiarism detection, and specifically, we propose an approach based on a fuzzy vectorial-based similarity. Given a suspicious melody, our approach envisions three steps: (1) its transformation in a vectorial representation, (2) retrieving of a list of similar melodies, (3) analysis and comparison with this subset of associated similar scores by using a fuzzy degree of similarity, that varies in a range between 0 for melodies that are fully musically different, and 1 for identical melodies. To assess the effectiveness of our system we performed tests on a large dataset of ascertained plagiarisms. Results show that it is able to reach an accuracy of 93%.

The plagiarism is a debated topic in different fields and in particular in music, given the huge amount of money that music is able to generate. Moreover, it is controversial aspect in the law's field given the subjectivity of the judges that have to pronounce on a suspicious case. Automatic detection of music plagiarism is fundamental to overcome these limits by representing an useful support for judges during their pronouncements and an important result to avoid musicians to spend more time in court than on composing and playing music. In this paper we address this issue by defining a new metric to discover pop music similarity and we study whether visualization can assist domain experts in judging suspicious cases. We describe a user study in which subjects performed different tasks on a song collection using different visual representations to investigate which one is best in terms of intuitiveness and accuracy. Results provided us with positive feedback about our choices and some useful suggestions for future directions.

Today's technology is redefining the way individuals can work, communicate, share experiences, constructively debate, and actively participate to any aspect of the daily life, ranging from business to education, from political and intellectual to social, and so on. Enabling access to technology by any individual, reducing obstacles, avoiding discrimination, and making the overall experience easier and enjoyable is an important objective of both research and industry.

Nowadays plagiarism is an interesting and debated topic in different fields. In music, the plagiarism is a very common phenomenon which touch the vast amounts of money that music melodies are able to generate in today's pop music market. In a music composition, the melody is assumed to be the most significant factor in a court's decision about whether a new music composition is an illegitimate version of a pre-existing composition. Despite the wide-spread belief that there is a fixed and trivial number of corresponding notes between two melodies, the similarity analysis is a very complex process. In this paper we address the plagiarism in pop music, and specifically, we study whether visualization can facilitate the task of discovering melodic similarities among musical songs. To investigate this, we defined three representations to show the melodic relations among songs. We performed a user study in which subjects performed different tasks on a song collection using these representations to investigate which one is best in terms of intuitiveness and accuracy. Results of the study provided us with positive feedback as well as further directions to explore.

With the end of Moore's Law in sight, parallelism became the main means for speeding up computationally intensive applications, especially in the cases where large collections of tasks need to be performed. Network supercomputing -- taking advantage of very large numbers of computers in a distributed environment is an effective approach to massive parallelism that harnesses the processing power inherent in large networked settings. In such settings, processor failures are no longer an exception, but the norm. Any algorithm designed for realistic settings must be able to deal with failures. This paper presents a new message-passing algorithm for distributed cooperative work in synchronous settings where processors may crash, and where any broadcasts performed by crashing processors are unreliable. We specify the algorithm, prove that it is correct, and perform extensive simulations that show that its performance is close to similar algorithms that use reliable broadcast, and that its work compares favorably to the relevant lower bounds.

Visual cryptography is a special type of secret sharing. Two models of visual cryptography have been independently studied: 1) deterministic visual cryptography, introduced by Naor and Shamir, and 2) random grid visual cryptography, introduced by Kafri and Keren. In this paper, we show that there is a strict relation between these two models. In particular, we show that to any random grid scheme corresponds a deterministic scheme and vice versa. This allows us to use results known in a model also in the other model. By exploiting the (many) results known in the deterministic model, we are able to improve several schemes and to provide many upper bounds for the random grid model and by exploiting some results known for the random grid model, we are also able to provide new schemes for the deterministic model. A side effect of this paper is that future new results for any one of the two models should not ignore, and in fact be compared with, the results known in the other model.

Music education for blind people heavily relies on Braille. The use of Braille for music causes difficulties for the blind student: new meanings for the Braille symbols have to be learned and the reading of the music is not immediate. More-over, in the majority of the cases, music teachers don't know Braille. Although Braille remains the primary means for music education for blind people, alternative methods can help. We propose a new methodology that helps the reading of music scores by means of a software that sings the name of the notes. Singing the name of the notes provides to a blind user a direct perception of the score. Moreover the information is directly conveyed to the student through the ear. Although the method has several limitations we believe that it is effective. The methodology is not intended to "replace" Braille, but only to offer a different approach to the study of music.

The use of computers in the production of artifacts has drawn the attention of both artists and computer scientists. Among the different art disciplines, music is one of the arts that most benefited from the use of computers. There are many works which demonstrate the great synergy between these two fields. In this paper we will focus on a specific music composition problem: the figured bass problem, in which we have to automatically generate a 4 voice piece of music, starting from an input the bass line. To solve this problem we use a hybrid strategy, in which different metaheuristics cooperate to find high quality solutions. The cooperation is controlled by means of the combination of fuzzy control and knowledge obtained through Data Mining. As will be shown in the experimental results section, this hybrid strategy is capable of finding musical solutions with an acceptable quality and never discordant which, according to experts, are sound and adhere to scholastic rule.

In this paper we consider the musical problem called unfigured bass harmonization: a bass line is given and the composer has to write other 3 voices to have a complete 4-voice piece of music with a 4-note chord for each bass note. Solving such a problem means finding appropriate chords to use for each bass note and also find a placement of the four notes within each chord so that melodic concerns are addressed, especially for the highest voice (soprano).We present a multi-objective genetic algorithm that automatically composes music when provided with a bass line input. The objectives considered are two: the harmonic objective (finding appropriate chords) and the melodic objective (find good melodic lines).

In this paper, we consider the problem of cheating for visual cryptography schemes. Although the problem of cheating has been extensively studied for secret sharing schemes, little work has been done for visual secret sharing. We provide a formal definition of cheating for visual cryptography and new (2, n)-threshold and (n, n)-threshold schemes that are immune to deterministic cheating.

We consider general resource assignment games involvingselfish users/agentsin which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the latency of their own traffic). We propose and study amechanism designapproach in which an allocation mechanism assigns users to resources and charges the users for using the resources so as to induce each user totruthfullyreport a private piece of information he/she holds (e.g., how much traffic he/she needs to transmit). This information is crucial for computing optimal (or close to optimal) allocations and an agent could misreport his/her information to induce the underlying allocation algorithm to output a solution which he/she likes more (e.g., which assigns better resources to him/her). For our resource allocation problems, we give analgorithmic characterizationof the solutions for which truth-telling is a Nash equilibrium. A natural application of these results is to a scheduling/routing problem which is the mechanism design counterpart of the selfish routing game of Koutsoupias and Papadimitriou [1999]: Each selfish user wants to route a piece of unsplittable traffic using one ofmlinks of different speeds so as to minimize his/herownlatency. Our mechanism design counterpart can be seen as the problem of schedulingselfish jobson parallel related machines and is the dual of the problem of scheduling (unselfish) jobs on parallelselfish machinesstudied by Archer and Tardos [2001]. Koutsoupias and Papadimitriou studied an “anarchic” scenario in which each user chooses his/her own link, and this may produce Nash equilibria of cost Ω(logm/log logm) times the optimum. Our mechanism design counterpart is a possible way of reducing the effect of selfish behavior via suitable incentives to the agents (i.e., taxes for using the links). We indeed show that in the resulting game, it is possible to guarantee an approximation factor of 8 for any number of links/machines (this solution also works for online settings). However, it remains impossible to guarantee arbitrarily good approximate solutions, even for 2 links/machines and even if the allocation algorithm is allowed superpolynomial time. This result shows that our scheduling problem with selfish jobs is more difficult than the scheduling problem with selfish machines by Archer and Tardos (which admits exact solutions). We also study some generalizations of this basic problem.

Visual cryptography schemes allow the encoding of a secret image, consisting of black or white pixels, into n shares which are distributed to the participants. The shares are such that only qualified subsets of participants can ‘visually’ recover the secret image. The secret pixels are shared with techniques that subdivide each secret pixel into a certain number m, m ≥ 2 of subpixels. Such a parameter m is called pixel expansion. Recently Yang introduced a probabilistic model. In such a model the pixel expansion m is 1, that is, there is no pixel expansion. The reconstruction of the image however is probabilistic, meaning that a secret pixel will be correctly reconstructed only with a certain probability. In this paper we propose a generalization of the model proposed by Yang. In our model we fix the pixel expansion m ≥ 1 that can be tolerated and we consider probabilistic schemes attaining such a pixel expansion. For m = 1 our model reduces to the one of Yang. For big enough values of m, for which a deterministic scheme exists, our model reduces to the classical deterministic model. We show that between these two extremes one can trade the probability factor of the scheme with the pixel expansion. Moreover, we prove that there is a one-to-one mapping between deterministic schemes and probabilistic schemes with no pixel expansion, where contrast is traded for the probability factor.

This paper introduces a methodology for estimating interdomain Web traffic lows between all clients worldwide and the ervers belonging to over one housand content providers. The idea is to use the server logs from a large ontent Delivery Network (CDN) to identify client downloads of content provider (i.e., publisher) Web pages. For each of these Web pages, a client typically downloads some objects from the content provider, some from the CDN, and perhaps some from third parties such as banner advertisement agencies. The sizes and sources of the non-CDN downloads associated with each CDN download are estimated separately by examining Web accesses in packet traces collected at several universities.

The Domain Name System (DNS) is a critical part of the Internet's infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few studies have been devoted to characterizing its properties, such as its workload and the stability of the top-level servers, many key components of DNS have not yet been examined. Based on large-scale measurements taken from servers in a large content distribution network, we present a detailed study of key characteristics of the DNS infrastructure, such as load distribution, availability, and deployment patterns of DNS servers. Our analysis includes both local DNS servers and servers in the authoritative hierarchy. We find that (1) the vast majority of users use a small fraction of deployed name servers, (2) the availability of most name servers is high, and (3) there exists a larger degree of diversity in local DNS server deployment and usage than for authoritative servers. Furthermore, we use our DNS measurements to draw conclusions about federated infrastructures in general. We evaluate and discuss the impact of federated deployment models on future systems, such as Distributed Hash Tables.

We study the problem of assigning unsplittable traffic to a set of m links so to minimize the maximum link congestion (i.e., the makespan). We consider the case of selfish agents owning pieces of the traffic. In particular, we introduce a variant of the model by Koutsopias and Papadimitriou [1999] in which owners of the traffic cannot directly choose which link to use; instead, the assignment is performed by a scheduler. The agents can manipulate the scheduler by reporting falseinformation regarding the size of each piece of unsplittable traffic.We provide upper and ower bounds on the approximation achievable by mechanisms that induce a Nash equilibrium when all agents report their true values.For the case of each agent owning one job, our positive results for m identical links show the effectiveness of introducing such a scheduler since, in this case, (1+ε)-approximate solutions are guaranteed in polynomial time. In contrast, the result by Koutsopias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash equilibria yield (in the worst case) Ω(log m over log log m)-approximate solutions, even for unitary weighted traffic. When links have different speeds we prove lower and upper bounds on the approximation achievable by a mechanism inducing a Nash equilibrium.Similar approximability results for identical machines have been achieved by Feldman et al. [2003]. However these results do not hold in our setting because their model assumes that the algorithm is provided with the correct traffic weights. For the case of agents owning more than one job, we give mechanisms that achieve constant approximation and prove lower bounds on the approximation ratio that can be achieved by a mechanism.

Nowadays email has become the most widely used means in daily communication on the net and is increasingly used in place of ordinary mail. Certified email protocols aim to provide additional properties to the standard email service. In this paper we provide a novel optimistic protocol for certified email satisfying nine of the most important properties usually considered in the literature. We give a formal description of the protocol with the input/output automation (IOA) framework and provide a prototype implementation for the Windows platform.

Visual cryptography schemes allow the encoding of a secret image into n shares which are distributed to the participants, such that only qualified subsets of participants can "visually" recover the secret image. In colored threshold visual cryptography schemes, the secret image is composed of pixels taken from a given set of c colors. We study c-color (k, n)-threshold visual cryptography schemes and provide a characterization of contrast optimal schemes. More specifically, we prove that there exists a contrast optimal scheme that is a member of a special set of schemes, which we call canonical schemes, and that satisfy strong symmetry properties. Then we use canonical schemes to provide a constructive proof of optimality, with respect to the pixel expansion, of c-color (n, n)-threshold visual cryptography schemes.

In this paper, we investigate the k-set consensus problem in asynchronous distributed systems. In this problem, each participating process begins the protocol with an input value and by the end of the protocol must decide on one value so that at most k total values are decided by all correct processes. We extend previous work by exploring several variations of the problem definition and model, including for the first time investigation of Byzantine failures. We show that the precise definition of the validity requirement, which characterizes what decision values are allowed as a function of the input values and whether failures occur, is crucial to the solvability of the problem. For example, we show that allowing default decisions in case of failures makes the problem solvable for most values of k despite a minority of failures, even in face of the most severe type of failures (Byzantine). We introduce six validity conditions for this problem (all considered in various contexts in the literature), and demarcate the line between possible and impossible for each case. In many cases, this line is different from the one of the originally studied k-set consensus problem.

In this paper we investigate the k-set consensus problem in asynchronous, message-passing distributed systems.In this problem, each participating process begins the protocol with an input value and by the end of the protocol must decide on one value so that at most k different values are decided by all correct processes.We extend previous work by exploring several variations of the problem definition and model, including for the first time investigation of Byzantine failures.We show that the precise definition of the validity requirement, which characterizes what decision values are allowed as a function of the input values and whether failures occur, is crucial to the solvability of the problem.For example, we show that allowing default decisions in case of failures makes the problem solvable for most values of k despite a minority of failures, even for the most severe type of failures (Byiantine).We introduce six validity conditions for this problem (all considered in various contexts in the literature), and demarcate the line between possible and impossible for each case.In many cases this line is different from the one of the originally studied k-set consensus problem.

View-oriented group communication services are widely used for fault-tolerant distributed computing.For applications involving coherent data, it is importaut to know when a process has a primary view of the current group membership, usually defined as a view containing a majority out of a static universe of processes.For high availability in a system where processes can join and leave routinely, some researchers have suggested def?.ning primary views dynamically, depending on having enough members in common with recent views.We present a new formal automaton specification, DVS, for the safety guarantees made by a practical group communication service providing a dynamic notion of primary view.We demonstrate the value of DVS by showing both how it can be implemented and how it can be used in an application.First, we present a distributed algorithm based on a group membership algorithm of Lotem, Keidar and Dolev; our version integrates communication with the membership service, uses iuformation from the application processes saying when a view has been prepared for computation by the application, and uses a static view-oriented service internally.We prove that this algorithm implements DVS.Second, we present an application algorithm that is a variant of an algorithm of Amir, Dolev, Keidar, Melliar-Smith and Moser, modified to use DVS instead of a static service.We prove that it implements a (non-group-oriented) totally-orderedbroadcast service.

While compressing a file with a Huffman code, it is possible that the size of the file grows temporarily. This happens when the source letters with low frequencies (to which long codewords are assigned) are encoded first. The maximum data expansion is the average growth in bits per source letter resulting from the encoding of a source letter with a long codeword. It is a measure of the worst case temporary growth of the file. In this paper we study the maximum data expansion of Huffman codes. We provide some new properties of the maximum data expansion δ of Huffman codes and using these properties we prove that δ < 1.256.

In this correspondence, we prove that the maximum data expansion /spl delta/ of Huffman codes is upper-bounded by /spl delta/<1.39. This bound improves on the previous best known upper bound /spl delta/<2. We also provide some characterizations of the maximum data expansion of optimal codes.

We provide new bounds on the expected length L of a binary one-to-one code for a discrete random variable X with entropy H. We prove that L/spl ges/H-log(H+1)-Hlog(1+1/H). This bound improves on previous results. Furthermore, we provide upper bounds on the expected length of the best code as function of H and the most likely source letter probability.

In this paper we continue the study of the path length of trees with known fringe as initiated by Klein and Wood (1989) and De Santis and Persiano (1994). We compute the path length of the minimal tree with given number of leaves N and fringe Δ for the case Δ ⩾ N/2. This complements the result of De Santis and Persiano (1994) that studied the case Δ ⩽ N/2. Our methods also yield a linear time algorithm for constructing the minimal tree when Δ ⩾ N/2.

Article Free Access Share on Time-optimal message-efficient work performance in the presence of faults Authors: Roberto De Prisco Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), Italy Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), ItalyView Profile , Alain Mayer Dept. of Computer Science, Columbia University, New York, NY Dept. of Computer Science, Columbia University, New York, NYView Profile , Moti Yung IBM Research Division T.J. Watson Research Center, Yorktown Heights, NY IBM Research Division T.J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 161–172https://doi.org/10.1145/197917.198082Published:14 August 1994Publication History 48citation208DownloadsMetricsTotal Citations48Total Downloads208Last 12 Months20Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF