Journals   (small normal full)
  1. "Extending IC-Scheduling via the Sweep Algorithm"
    with Grzegorz Malewicz and Arnold L. Rosenberg.
    In Journal of Parallel and Distributed Computing - Elsevier (JPDC), Vol. 70 Issues 3, ISSN: 0743-7315, Pages 201-211, March 2010.
    Abstract. A key challenge when scheduling computations over the Internet is {\em temporal unpredictability:} remote ``workers'' arrive and depart at unpredictable times and often provide unpredictable computational resources; the time for communication over the Internet is impossible to predict accurately. In response, earlier research has developed the underpinnings of a theory of how to schedule computations having intertask dependencies in a way that renders tasks eligible for execution at the maximum possible rate. Simulation studies suggest that such scheduling: ($a$) utilizes resource providers' computational resources well, by enhancing the likelihood of having work to allocate to an available client; ($b$) lessens the likelihood of a computation's stalling for lack of tasks that are eligible for execution. The applicability of the current version of the theory is limited by its demands on the structure of the {\sc dag} that models the computation being scheduled---namely, that the {\sc dag} be decomposable into {\em connected} bipartite ``building-block'' {\sc dag}s. The current paper extends the theory by developing the {\em Sweep Algorithm}, which takes a significant step toward removing this restriction. The resulting augmented suite of scheduling algorithms allows one to craft optimal schedules for a large range of {\sc dag}s that the earlier framework could not handle. Most of the newly optimally scheduled {\sc dag}s presented here are artificial but ``close'' in structure to {\sc dag}s that arise in real computations; one of the new {\sc dag}s is a component of a large {\sc dag} that arises in a functional Magnetic Resonance Imaging application.
    (pdf)

  2. "Navigable Small–World Networks with Few Random Bits"
    with Luisa Gargano.
    In Theoretical Computer Science - Elsevier (TCS), Vol. 410 Issues 47-49, ISSN: 0304-3975, Pages 4975-4988, November 2009.
    Abstract. We study Small–World graphs in the perspective of their use in the development of efficient as well as easy to implement network infrastructures. Our analysis starts from the Small–World model proposed by Kleinberg: a grid network augmented with directed long–range random links. The choices of the long–range links are independent from one node to another. In this setting greedy routing and some of its variants have been analyzed and shown to produce paths of polylogarithmic expected length. We start from asking whether all the randomness, used in the Kleinberg’s model for establishing the long–range contacts of the nodes, is indeed necessary to assure the existence of short paths. In order to deal with the above question, we impose (stringent) restrictions on the choice of long–range links and we show that such restrictions do not increase the average path length of greedy routing and of its variations. We are able to decrease the number of random bits, required to establish each node’s long–range link, from \Omega(log n) to O(log log n) on a network of size n. Diminishing the randomness in the choice of random links has several benefits; in particular, it implies an increase in the clustering of the graph, thus increasing the resilience of the network.
    (pdf)

  3. "Degree-Optimal Routing for P2P Systems"
    with Giovanni Chiola, Luisa Gargano, Alberto Negro and Vittorio Scarano.
    In Theory of Computing Systems (ToCS), Vol. 45 No. 1, ISSN: 1432-4350, pages 43-63, June 2009.
    Abstract. We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks—e.g. optimal average path length O(log^2 n / \delta log \delta) with d degree—with the programmability and startup efficiency of a uniform overlay—that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that \Omega(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151–163, 2004). Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows us to achieve optimal average path length in randomized networks. The advantage of our proposal is that of allowing the NoN technique to be implemented without adding any overhead to the corresponding deterministic network. We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. By varying the value c, the system goes from the deterministic case (c = 1) to an “almost uniform” system. Increasing c to relatively low values allows for routing with asymptotically optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system.
    (pdf)

  4. "Experiences with Mesh-like computations using Prediction Binary Trees"
    with Biagio Cosenza, Rosario De Chiara, Ugo Erra, and Vittorio Scarano.
    In Scalable Computing: Practice and Experience, Scientific International Journal for Parallel and Distributed Computing (SCPE), Vol. 10, ISSN: 1895-1767, pages 173-187, June 2009.
    Abstract. In this paper we aim at exploiting the temporal coherence among successive phases of a computation, in order to implement a load-balancing technique in mesh-like computations to be mapped on a cluster of processors. A key concept on which the load balancing schema is built on the use of a Predictor component that is in charge of providing an estimation of the unbalancing between successive phases. By using this information, our method partitions the computation in balanced tasks through the Prediction Binary Tree (PBT). At each new phase, current PBT is updated by using previous phase computing time (for each task) as (next phase) cost estimate. The PBT is designed so that it balances the load across the tasks as well as reduces {\em dependency} among processors for higher performances. Reducing dependency is obtained by using rectangular tiles of the mesh, of almost-square shape (i.e. one dimension is at most twice the other). By reducing dependency, one can reduce inter-processors communication or exploit local dependencies among tasks (such as data locality). Furthermore, we also provide two heuristics which take advantage of data-locality. Our strategy has been assessed on a significant problem, Parallel Ray Tracing. Our implementation shows a good scalability, and improves performance in both cheaper commodity cluster and high performance clusters with low latency networks. We report different measurements showing that tasks granularity is a key point for the performances of our decomposition/mapping strategy.
    (pdf)

  5. "F-Chord: Improved Uniform Routing on Chord"
    with Luisa Gargano, Mikael Hammar, Alberto Negro and Vittorio Scarano.
    In Networks (Wiley), Vol. 52 No. 4, ISSN: 0028-3045, pages 325-332, December 2008.
    Abstract. We propose a family of novel Chord-based P2P schemes retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes, based on the Fibonacci number system, allow to simultaneously improve on the maximum/average number of hops for lookups and the routing table size per node.
    (pdf)

  6. "Optimizing the finger tables in Chord-like DHTs"
    with Giovanni Chiola, Luisa Gargano, Alberto Negro and Vittorio Scarano.
    In Concurrency and Computation: Practice and experience (Wiley), Vol. 20 No. 6, ISSN: 1532-0634, pages 643-657, April 2008.
    Abstract. The Chord protocol is the best known example of implementation of logarithmic complexity routing for structured peer-to-peer networks. Its routing algorithm, however, does not provide an optimal trade-off between resources exploited (the size of the “finger table”) and performance (the average or worst-case number of hops to reach destination). Cordasco et al. showed that a finger table based on Fibonacci distances provides lower number of hops with fewer table entries. In this paper we generalize this result, showing how to construct an improved finger table when the objective is to reduce the number of hops, possibly at the expense of an increased size of the finger table. Our results can also be exploited to guarantee low routing time in case a fraction of nodes fails.
    (pdf)

  7. "Advances in IC-Scheduling Theory: Scheduling Expansive and Reductive Dags and Scheduling Dags via Duality"
    with Grzegorz Malewicz and Arnold L. Rosenberg.
    In IEEE Transaction on Parallel and Distributed Systems (TPDS), Vol. 18, No. 11, ISSN: 1045-9219, November 2007.
    Abstract. Earlier work has developed the underpinnings of the IC-Scheduling Theory, a framework for scheduling computations having intertask dependencies—modeled via directed acyclic graphs (DAGs)—for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients’ computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation’s stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation ., which allows one to “prioritize” the scheduling of a complex DAG’s building blocks. The current paper extends the IC-Scheduling Theory in two ways: by expanding significantly the repertoire of DAGs that the Theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either “expansive,” in the sense that they grow outward from their sources, or “reductive,” in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to “read off” an optimal schedule for a DAG from a given optimal schedule for the DAG’s dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks).
    (pdf)

  8. "Bounded-Collision Memory-Mapping Schemes for Data Structures, with Applications to Parallel Memories"
    with Vittorio Scarano and Arnold L. Rosenberg.
    In IEEE Transaction on Parallel and Distributed Systems (TPDS), Vol. 18, No. 7, ISSN: 1045-9219, July 2007.
    Abstract. Techniques are developed for mapping structured data to an ensemble of parallel memory modules in a way that limits the number of conflicts, i.e., simultaneous accesses by distinct processors to the same memory module. The techniques determine, for any given conflict tolerance c, the smallest ensemble that allows one to store any n-node data structure “of typeX” in such a way that no more than c nodes of a structure are stored on the same module. This goal is achieved by determining the smallest c-perfect universal graphs for data structures “of type X.” Such a graph is the smallest graph that contains a homomorphic image of each n-node structure “of type X,” with each node of the image holding  c nodes of the structure. In the current paper, "type X" refers to rooted binary trees and three array-like structures: chaotic arrays, ragged arrays, and rectangular arrays. For each of these families of data structures, the number of memory modules needed to achieve conflict tolerance c is determined to within constant factors.
    (pdf)
Conferences
  1. "Some Considerations on the Design of a P2P Infrastructure for Massive Simulations" with Rosario De Chiara,Ugo Erra, and Vittorio Scarano. In International Conference on Ultra Modern Telecommunication (ICUMT 2009). October 2009, St.-Petersburg, Russia. (pdf, talk)
  2. "Interactive Visual Classification with Euler Diagrams" with Rosario De Chiara, Andrew Fish. In Proc. of IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2009). September 2009, Corvallis, Oregon, USA. (pdf, talk)
  3. "On Scheduling Dags to Maximize Area" with Arnold L. Rosenberg. In Proc. of IEEE International Parallel & Distributed Processing Symposium (IPDPS 2009). May 2009, Rome, Italy. (pdf, talk)
  4. "Relaxed-2-Chord: Efficiency, Flexibility and provable Stretch" with Francesca Della Corte, Alberto Negro, Alessandra Sala and Vittorio Scarano. In Proc. of Sixth International Workshop on Hot Topics in Peer-to-Peer Systems (HotP2P 2009), held in conjunction with the IEEE International Parallel & Distributed Processing Symposium (IPDPS 2009). May 2009, Rome, Italy. (pdf, talk)
  5. "On Clustering Tasks in IC-Optimal Dags" with Mark Sims and Arnold L. Rosenberg. In Proc. of International Conference on Parallel Processing (ICPP 2008). September 8–12, Portland, Oregon, USA. (pdf)
  6. "On Estimating the Effectiveness of Temporal and Spatial Coherence in Parallel Ray Tracing" with Biagio Cosenza, Rosario De Chiara, Ugo Erra, and Vittorio Scarano. In Proc. of 6th Eurographics Italian Chapter Conference (EG_It 2008). July 2-4, Salerno, Italy. (pdf)
  7. "Load Balancing in Mesh-like Computations using Prediction Binary Trees" with Biagio Cosenza, Rosario De Chiara, Ugo Erra, and Vittorio Scarano. In Proc. of 7th International Symposium on Parallel and Distributed Computing (ISPDC 2008). July 1-5, Krakow, Poland. (pdf, talk)
  8. "Extending IC-Scheduling via the Sweep Algorithm" with Grzegorz Malewicz and Arnold L. Rosenberg. In Proc. of 16th Euromicro Conference on Parallel Distributed and network-based Processing (PDP 2008) ISBN 0-7695-3089-3, pages 366-373, February 13-15, 2008 - Toulouse, France. (postscript, pdf, talk)
  9. "PON: Exploiting Proximity on Overlay Networks"  with Alberto Negro, Alessandra Sala and Vittorio Scarano. In Proc. of Fourth International Workshop on Hot Topics in Peer-to-Peer Systems (HotP2P 2007) held in conjunction with the IEEE International Parallel & Distributed Processing Symposium (IPDPS 2007) March 30, 2007 Long Beach, California U.S.A. (pdf)
  10. "Applying IC-Scheduling Theory to Familiar Classes of Computations"  with Grzegorz Malewicz and Arnold L. Rosenberg. In Proc. of Workshop on Large-Scale, Volatile Desktop Grids (PCGrid 2007) held in conjunction with the IEEE International Parallel & Distributed Processing Symposium (IPDPS 2007) March 30, 2007 Long Beach, California U.S.A. (pdf)
  11. "How Much Independent Should Individual Contacts be to Form a Small-World?"  with Luisa Gargano. In Proc. of The 17th International Symposium on Algorithms and Computation (ISAAC 2006) December 18-20, 2006 - Kolkata, India. (postscript, pdf, ppt)
  12. "On Scheduling Expansive and Reductive Dags for Internet-Based Computing"  with Grzegorz Malewicz and Arnold L. Rosenberg. In Proc. of The 26th International Conference on Distributed Computing Systems (ICDCS 2006) July 4-7, 2006 - Lisboa, Portugal. (postscript, pdf, ppt)
  13. "Optimizing the finger table in Chord-like DHTs"  with Giovanni Chiola, Luisa Gargano , Alberto Negro and Vittorio Scarano. In Proc. of Third International Workshop on Hot Topics in Peer-to-Peer Systems (HotP2P 2006) (Co-Located with IPDPS 2006) Rhodes Island, Greece. April 29, 2006. (postscript, pdf, ppt)
  14. "Overlay networks with class" with Giovanni Chiola, Luisa Gargano, Alberto Negro and Vittorio Scarano. In Proc. of 8th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2005) Las Vegas, Nevada, USA. December 7-9, 2005. (postscript, pdf)
  15. "2-Chord Halved" with Alessandra Sala. In Proc. of Second International Workshop on Hot Topics in Peer-to-Peer Systems (Hot-P2P05) (Co-Located with Mobiquitous 2005) San Diego, CA, USA. July 21, 2005. (postscript, pdf)
  16. "Degree-Optimal Deterministic Routing for P2P Systems" with Luisa Gargano, Mikael Hammar and Vittorio Scarano. In Proc. of 10th IEEE Symposium on computers and communications (ISCC 2005) La Manga del Mar Menor, Cartagena, SPAIN June 27-30, 2005. (postscript, pdf)
  17. "Non-uniform deterministic routing on F-Chord(α)" with Luisa Gargano, Mikael Hammar, Alberto Negro and Vittorio Scarano. In Proc. of First International Workshop on Hot Topics in Peer-to-Peer Systems (Hot-P2P04) Volendam (The Netherland) October 08, 2004. (postscript, pdf, ppt) (pictures)
  18. "A P2P Distributed Adaptive Directory" with Vittorio Scarano and Cristiano Vitolo. In Proc. of Adaptive Hypermedia 2004 (AH04) Eindhoven (The Netherland) August 23-26, 2004. (postscript, pdf, ppt) (pictures)
  19. "Brief Announcement: Degree-Optimal Deterministic Routing for P2P Systems" with Luisa Gargano, Mikael Hammar and Vittorio Scarano. In Proc. of Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004) (Brief Announcement) St. John's, Newfoundland, Canada July 25-28, 2004.(postscript, pdf)
  20. "F-Chord: Improved Uniform Routing on Chord"  with Luisa Gargano, Mikael Hammar, Alberto Negro and Vittorio Scarano. In Proc. of 11th Colloquium on Structural Information and Communication Complexity (Sirocco) Smolenice Castle, Slovakia June 21-23, 2004. (postscript, pdf, ppt) (pictures)
  21. "Architecture of a P2P Distributed Adaptive Directory" with Vittorio Scarano and Cristiano Vitolo. In Proc. of 13th International World Wide Web Conference (WWW04)(Poster) New York May 17-22, 2004.(postscript, pdf, poster)
  22. "c-Perfect Hashing Schemes for Binary Trees, with Applications to Parallel Memories"  with Alberto Negro, Arnold L. Rosenberg and Vittorio Scarano. International Conference on Parallel and Distributed Computing (EuroPar) Klagenfurt (Osterreich) August 26-29, 2003. (postscript, pdf, ppt) (pictures)
  23. "c-Perfect Hashing Schemes for Arrays, with Applications to Parallel Memories" with Alberto Negro, Arnold L. Rosenberg and Vittorio Scarano. Fifth Workshop on Distributed Data and Structures (WDAS) Thessaloniki (Greece), June 13-14, 2003. (postscript, pdf, ppt) (pictures)
PhD Thesis   (small normal full)
  • "On Designing Overlay Networks for Peer-to-Peer Systems"
    Abstract. Over the last five years, Peer-to-Peer (P2P) networking has generated a tremendous amount of interest world-wide among both Internet surfers and computer networking professionals. As a matter of fact since May 1999 when Shawn Fanning launched the first P2P file-sharing application, Napster, the phenomenon of file-sharing has continued to sensationally grow in popularity and appears set to remain an important feature of the Internet for the immediate future. However, as this dissertation will argue, P2P is much more than just a way of exchanging MP3s over the Internet. Peer-to-Peer systems rely on the computing power and bandwidth of the participants in the network (peers) rather than concentrating it in a relatively few servers. One of the most important benefits provided by P2P systems is the "Scalability". In a P2P systems, each consumer of the resources also donates resources. Nevertheless, "Scalability" has been recognized as the central challenge in designing such systems. Unfortunately, the initial designs for P2P systems had significant scaling problems. Thus, the chaotic, ad hoc topologies of the first-generation Peer-to-Peer architectures have been replaced by a set of topologies with an emergent order, provable properties as well as excellent performance. Indeed, several research groups have – independently – proposed the second generation of P2P systems (DHT systems) that support a Distributed Hash Table (DHT) functionality. In a DHT system, files and peers are associated with a key and each peer in the system is responsible for storing a certain range of keys. Peers set up direct connections among themselves based on their key and form an overlay network with each node having several other peers as neighbors. These connection are used for routing messages between the peers. Chord is one of the most popular DHT system proposed in the literature. It implements the idea of “consistent hashing” to build the Distributed Hash Table (DHT) based on several independent nodes and exhibits an overlay network with logarithmic node degree and diameter. In this dissertation the design and implementation of overlay networks based on DHTs are discussed with the main features of this contribution being: (i) The proposal of a family of novel Peer-to-Peer overlay networks, based on the Fibonacci number system, retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes proposed simultaneously improve on the maximum/average number of hops for lookups and the routing table size per node. (ii)The proposal of routing schemes that optimize the average number of hops for lookup requests in Peer-to-Peer overlay networks. This work is inspired by the recently introduced variation of greedy routing, called neighbor-of-neighbor (NoN), which allows an optimal average path length with respect to the degree to be obtained. This strategy does not make use of randomization and as a consequence, the NoN technique can be implemented within these schemes without adding any overhead. Analyzed networks include several popular topologies: Chord, F-Chord(\alpha), Hypercube based networks, Symphony, Skip-graphs. The improvement is obtained with no harm to the operational efficiency (e.g. stability, ease of programming, scalability, fault-tolerance) of the considered systems. (iii) The proposal of a family of Distributed Hash Table systems with the aim of combining routing efficiency of the randomized networks – average path length O(log n / log log n) vs. the O(log n) average path length of the deterministic system – with the programmability and start-up efficiency of a uniform system – i.e., a system in which the overlay network is transitive and greedy routing optimal. The proposed family is parameterized with a positive integer c which measures the amount of randomness that is used. Varying the value c, the system goes from the deterministic case (c = 1) to an “almost uniform” system. Increasing c to relatively low values allows routing with optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system. A matching lower bound for the average path length of the family of routing schemes for any c is also given.
    (Abstract) (pdf) (Presentation)


Désirée pictures (more) ... sometimes dreams come true!!!

Favorite Links


Gennaro Cordasco

Dipartimento di Informatica ed Applicazioni "R.M. Capocelli"
Universita' di Salerno
Fisciano (SA) -- 84084 ITALY
e-mail: cordasco[at]dia.unisa.it
Gennaro