Change search
Refine search result
1 - 16 of 16
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Aurell, Erik
    et al.
    KTH, School of Engineering Sciences (SCI), Physics.
    El-Ansary, Sameh
    KTH, School of Engineering Sciences (SCI), Physics.
    A physics-style approach to scalability of distributed systems2005In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 3267, p. 266-272Article in journal (Refereed)
    Abstract [en]

    Is it possible to treat large scale distributed systems as physical systems? The importance of that question stems from the fact that the behavior of many P2P systems is very complex to analyze analytically, and simulation of scales of interest can be prohibitive. In Physics, however, one is accustomed to reasoning about large systems. The limit of very large systems may actually simplify the analysis. As a first example, we here analyze the effect of the density of populated nodes in an identifier space in a P2P system. We show that while the average path length is approximately given by a function of the number of populated nodes, there is a systematic effect which depends on the density. In other words, the dependence is both on the number of address nodes and the number of populated nodes, but only through their ratio. Interestingly, this effect is negative for finite densities, showing that an amount of randomness somewhat shortens average path length.

  • 2.
    El-Ansary, Sameh
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    A component-based P2P simulation environmentManuscript (preprint) (Other academic)
  • 3.
    El-Ansary, Sameh
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    A structured P2P overlay networks primerManuscript (preprint) (Other academic)
  • 4.
    El-Ansary, Sameh
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Designs and analyses in structured peer-to-peer systems2005Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Peer-to-Peer (P2P) computing is a recent hot topic in the areas of networking and distributed systems. Work on P2P computing was triggered by a number of ad-hoc systems that made the concept popular. Later, academic research efforts started to investigate P2P computing issues based on scientific principles. Some of that research produced a number of structured P2P systems that were collectively referred to by the term ``Distributed Hash Tables'' (DHTs). However, the research occurred in a diversified way leading to the appearance of similar concepts yet lacking a common perspective and not heavily analyzed. In this thesis we present a number of papers representing our research results in the area of structured P2P systems grouped as two sets labeled respectively ``Designs'' and ``Analyses''.

    The contribution of the first set of papers is as follows. First, we present the principle of distributed k-ary search (DKS) and argue that it serves as a framework for most of the recent P2P systems known as DHTs. That is, given the DKS framework, understanding existing DHT systems is done simply by seeing how they are instances of that framework. We argue that by perceiving systems as instances of the DKS framework, one can optimize some of them. We illustrate that by applying the framework to the Chord system, one of the most established DHT systems. Second, We show how the DKS framework helps in the design of P2P algorithms by two examples: (a) The DKS(n;k;f) system which is a system designed from the beginning on the principles of distributed k-ary search. (b) Two broadcast algorithms that take advantage of the distributed k-ary search tree.

    The contribution of the second set of papers is as follows. We account for two approaches that we used to evaluate the performance of a particular class of DHTs, namely the one adopting periodic stabilization for topology maintenance. The first approach was of an intrinsic empirical nature. In that approach, we tried to perceive a DHT as a physical system and account for its properties in a size-independent manner. The second approach was of a more analytical nature. In this approach we applied the technique of Master equations, which is a widely used technique in the analysis of natural systems. The application of the technique lead to a highly accurate description of the behavior of structured overlays.

    Additionally, the thesis contains a primer on structured P2P systems that tries to capture the main ideas that are prevailing in the field and enumerates a subset of the current hot and open research issues.

  • 5.
    El-Ansary, Sameh
    et al.
    Distributed Systems Lab, SICS-Swedish Institute of Computer Science.
    Aurell, Erik
    KTH, Superseded Departments, Physics.
    Brand, Per
    Distributed Systems Lab, SICS-Swedish Institute of Computer Science.
    Haridi, Seif
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Experience with a physics-style approach for the study of self properties in structured overlay networks2004In: SELF-STAR: International Workshop on Self-* Properties in Complex Information Systems, May 2004, Bertinoro, Italy, 2004Conference paper (Other academic)
    Abstract [en]

    This paper gives a brief summary of our experience in applying a physics-style approach for analyzing the behavior of structured overlay networks that deploy self-organization and self-repair policies. Such systems are not always simple to model analytically and simulation of scales of interest can be prohibitive. Physicists deal with scale by characterizing a system using intensive variables, i.e. variables that are size independent. The approach proved its substantial usefulness when applied to satisfiability theory and it is the hope that it can be as useful in the field of large-scale distributed systems. We report here our finding of one simple self-organization-related intensive variable, and a more complex self-repair-related intensive variable.

  • 6.
    El-Ansary, Sameh
    et al.
    Swedish Institute of Computer Science (SICS).
    Aurell, Erik
    KTH, School of Engineering Sciences (SCI), Physics.
    Haridi, Seif
    KTH, School of Engineering Sciences (SCI), Physics.
    A physics-inspired performance evaluation of a structured peer-to-peer overlay network2005In: IASTED International Conference on Parallel and Distributed Computing and Networks, as part of the 23rd IASTED International Multi-Conference on Applied Informatics: Innsbruck: 15 February 2005 through 17 February 2005, 2005, p. 116-122Conference paper (Refereed)
    Abstract [en]

    In the majority of structured peer-to-peer overlay networks a graph with a desirable topology is constructed. In most cases, the graph is maintained by a periodic activity performed by each node in the graph to preserve the desirable structure in face of the continuous change of the set of nodes. The interaction of the autonomous periodic activities of the nodes renders the performance analysis of such systems complex and simulation of scales of interest can be prohibitive. Physicists, however, are accustomed to dealing with scale by characterizing a system using intensive variables, i.e. variables that are size independent. The approach has proved its usefulness when applied to satisfiability theory. This work is the first attempt to apply it in the area of distributed systems. The contribution of this paper is two-fold. First, we describe a methodology to be used for analyzing the performance of large scale distributed systems. Second, we show how we applied the methodology to find an intensive variable that describe the characteristic behavior of the Chord overlay network, namely, the ratio of the magnitude of perturbation of the network (joins/failures) to the magnitude of periodic stabilization of the network.

  • 7.
    El-Ansary, Sameh
    et al.
    Distributed Systems Laboratory, SICS Swedish Institute of Computer Science.
    Aurell, Erik
    KTH, School of Engineering Sciences (SCI), Physics.
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Physics-inspired performance evaluation of DHTsManuscript (preprint) (Other academic)
    Abstract [en]

    In the majority of structured peer-to-peer overlay networks a graph with a desirable topology is constructed. In most cases, the graph is maintained by a periodic activity performed by each node in the graph to preserve the desirable structure in face of the continuous change of the set of nodes. The interaction of the autonomous periodic activities of the nodes renders the performance analysis of such systems complex and simulation of scales of interest can be prohibitive. Physicists, however, are accustomed to dealing with scale by characterizing a system using intensive variables, i.e. variables that are size independent. The approach has proved its usefulness when applied to satisfiability theory. This work is the first attempt to apply it in the area of distributed systems. The contribution of this paper is two-fold. First, we describe a methodology to be used for analyzing the performance of large scale distributed systems. Second, we show how we applied the methodology to find two intensive variables that describe the characteristic behavior of the Chord overlay network, the variables are: 1) The density of nodes in the identifier space and 2) The ratio of the magnitude of perturbation of the network (joins/failures) to the magnitude of periodic stabilization of the network.

  • 8.
    El-Ansary, Sameh
    et al.
    Swedish Institute of Computer Science (SICS).
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    An overview of structured P2P overlay networks2006In: Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks / [ed] Jie Wu, Auerbach Publications , 2006Chapter in book (Other academic)
  • 9.
    El-Ansary, Sameh
    et al.
    Distributed Systems Laboratory, SICS Swedish Institute of Computer Science.
    Krishnamurthy, Supriya
    Distributed Systems Laboratory, SICS Swedish Institute of Computer Science.
    Aurell, Erik
    KTH, Superseded Departments, Physics.
    Haridi, Seif
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    An Analytical Study of Consistency and Performance of DHTs under Churn2004Report (Other academic)
    Abstract [en]

    In this paper, we present a complete analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a master-equation-based approach, which is used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. We demonstrate that this methodology is infact also well suited to describing structured overlay networks by an application to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of: the distribution of inter-node distances, the probability of network disconnection, the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict both the performance and consistency of lookups under churn. Additionally, we also discuss how churn may actually be of different 'types' and the implications this will have for structured overlays in general. All theoretical predictions match simulation results to a high extent. The analysis includes details that are applicable to a generic structured overlay deploying a ring as well as Chord-specific details that can act as guidelines for analyzing other systems.

  • 10.
    El-Ansary, Sameh
    et al.
    Distributed Systems Laboratory, SICS Swedish Institute of Computer Science.
    Krishnamurthy, Supriya
    Distributed Systems Laboratory, SICS Swedish Institute of Computer Science.
    Aurell, Erik
    KTH, School of Engineering Sciences (SCI), Physics.
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Analytical study of consistency and performance of DHTs under churnManuscript (preprint) (Other academic)
    Abstract [en]

    In this paper, we present a complete analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a master-equation-based approach, which is used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. We demonstrate that this methodology is infact also well suited to describing structured overlay networks by an application to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of: the distribution of inter-node distances, the probability of network disconnection, the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict both the performance and consistency of lookups under churn. Additionally, we also discuss how churn may actually be of different ’types’ and the implications this will have for structured overlays in general. All theoretical predictions match simulation results to a high extent. The analysis includes details that are applicable to a generic structured overlay deploying a ring as well as Chord-specific details that can act as guidelines for analyzing other systems.

  • 11.
    El-Ansary, Sameh
    et al.
    Swedish Institute of Computer Science.
    Onana Alima, Luc
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Brand, Per
    Swedish Institute of Computer Science.
    Haridi, Seif
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    A Framework for Peer-To-Peer Lookup Services based on k-ary search2002Report (Other academic)
    Abstract [en]

    Locating entities in peer-to-peer environments is a fundamentaloperation. Recent studies show that the concept of distributed hash table can be used to design scalable lookup schemes with good performance (i.e. small routing table and lookup length). In this paper, we propose a simple framework for deriving decentralized lookup algorithms. The proposed framework is simple in that it is based on the well-known concept of k-ary search. To demonstrate the applicability of our framework, we show how it can be used to instantiate Chord. When deriving a generalized Chord from our framework, we obtain better performance in terms of the routing table size (38% smaller than the generalization suggested by the Chord authors).

  • 12.
    El-Ansary, Sameh
    et al.
    Swedish Institute of Computer Science.
    Onana Alima, Luc
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Brand, Per
    Swedish Institute of Computer Science.
    Haridi, Seif
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Efficient broadcast in structured P2P networks2003In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 2735, p. 304-314Article in journal (Refereed)
    Abstract [en]

    In this position paper, we present an efficient algorithm for performing a broadcast operation with minimal cost in structured DHT-based P2P networks. In a system of N nodes, a broadcast message originating at an arbitrary node reaches all other nodes after exactly N - 1 messages. We emphasize the perception of a class of DHT systems as a form of distributed k-ary search and we take advantage of that perception in constructing a spanning tree that is utilized for efficient broadcasting. We consider broadcasting as a basic service that adds to existing DHTs the ability to search using arbitrary queries as well as dissiminate/collect global information.

  • 13.
    Ghodsi, Ali
    et al.
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Onana Alima, Luc
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    El-Ansary, Sameh
    Swedish Institute of Computer Science.
    Brand, Per
    Swedish Institute of Computer Science.
    Haridi, Seif
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Self-Correcting Broadcast in Distributed Hash Tables2003In: Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems / [ed] Gonzalez, T., 2003, p. 93-98Conference paper (Refereed)
    Abstract [en]

    We present two broadcast algorithms that can be used on top of distributed hash tables (DHTs) to perform group communication and arbitrary queries. Unlike other P2P group communication mechanisms, which either embed extra information in the DHTs or use random overlay networks, our algorithms take advantage of the structured DHT overlay networks without maintaining additional information. The proposed algorithms do not send any redundant messages. Furthermore the two algorithms ensure 100% coverage of the nodes in the system even when routing information is outdated as a result of dynamism in the network. The first algorithm performs some correction of outdated routing table entries with a low cost of correction traffic. The second algorithm exploits the nature of the broadcasts to extensively update erroneous routing information at the cost of higher correction traffic. The algorithms are validated and evaluated in our stochastic distributed-algorithms simulator.

  • 14.
    Krishnamurthy, Supriya
    et al.
    Swedish Institute of Computer Science.
    El-Ansary, Sameh
    Swedish Institute of Computer Science.
    Aurell, Erik
    KTH, School of Engineering Sciences (SCI), Physics.
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    A statistical theory of Chord under churn2005In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 3640, p. 93-103Article in journal (Refereed)
    Abstract [en]

    Most earlier studies of DHTs under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation- based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different 'types' and the implications this will have for the functioning of DHTs in general.

  • 15.
    Krishnamurthy, Supriya
    et al.
    KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
    El-Ansary, Sameh
    Swedish Institute of Computer Science (SICS).
    Aurell, Erik
    KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    An analytical study of a structured overlay in the presence of dynamic membership2008In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 16, no 4, p. 814-825Article in journal (Refereed)
    Abstract [en]

    In this paper, we present an analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a fluid model approach to describe steady-state or transient phenomena and apply it to the Chord system. For any rate of churn and stabilization rates and any system size, we accurately account for the functional form of the probability of network disconnection as well as the fraction of failed or incorrect successor and finger pointers. We show how we can use these quantities to predict both the performance and consistency of lookups under churn. All theoretical predictions match simulation results. The analysis includes both features that are generic to structured overlays deploying a ring as well as Chord-specific details and opens the door to a systematic comparative analysis of, at least, ring-based structured overlay systems under churn.

  • 16.
    Onana Alima, Luc
    et al.
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    El-Ansary, Sameh
    Swedish Institute of Computer Science.
    Brand, Per
    Swedish Institute of Computer Science.
    Haridi, Seif
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    DKS(N, k, f): A family of low communication, scalable and fault-tolerant infrastructures for P2P applications2003In: CCGRID 2003: 3RD IEEE/ACM INTERNATIONAL SYMPOSIUM ON CLUSTER COMPUTING AND THE GRID, PROCEEDINGS / [ed] Titsworth, F.; Azada, D., LOS ALAMITOS: IEEE COMPUTER SOC , 2003, p. 344-350Conference paper (Refereed)
    Abstract [en]

    In this paper, we present EKS(N,k,f), a family of infrastructures for building Peer-To-Peer applications. Each instance of EKS(N,k,f) is a fully decentralized overlay network characterized by three parameters: N the maximum number of nodes that can be in the network; k the search arity within the network and f the degree of fault-tolerance. Once these parameters are instantiated, the resulting network has several desirable properties. The first property, which is the main contribution of this paper, is that there is no separate procedure for maintaining routing tables; instead, any out-of-date or erroneous routing entry is eventually corrected on-the-fly thereby, eliminating unnecessary bandwidth consumption. The second property is that each lookup request is resolved in at Most log(k)(N) overlay hops under normal operations. Third, each node maintains only (k - 1) log(k)(N) + 1 addresses of other nodes for routing purposes. Fourth, new nodes can join and existing nodes can leave at will with a negligible disturbance to the ability to resolve lookups in logk(N) hops in average. Fifth, any pair key/value that is inserted into the system is guaranteed to be located even in the presence of concurrent joins. Sixth, even if f consecutive nodes fail simultaneously, correct lookup is still guaranteed.

1 - 16 of 16
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf