Change search
Refine search result
1 - 14 of 14
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.
    Arad, Cosmin
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Shafaat, Tallat Mahmood
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Brief announcement: Atomic consistency and partition tolerance in scalable key-value stores2012In: Distributed Computing: 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings / [ed] Marcos K. Aguilera, Springer, 2012, p. 445-446Conference paper (Refereed)
    Abstract [en]

    We propose consistent quorums to achieve linearizability in scalable and self-organizing key-value stores based on consistent hashing.

  • 2. Bordencea, D.
    et al.
    Shafaat, Tallat Mahmood
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Arad, Cosmin
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Valean, H.
    Efficient linearizable write operations using bounded global time uncertainty2013In: Proceedings - 2013 IEEE 12th International Symposium on Parallel and Distributed Computing, ISPDC 2013, IEEE , 2013, p. 59-66Conference paper (Refereed)
    Abstract [en]

    Distributed key-value stores employed in data centers treat each key-value pair as a shared memory register. For fault-tolerance and performance, each key-value pair is replicated. Various models exist for the consistency of data amongst the replicas. While atomic consistency, also known as linearizability, provides the strongest form of consistency for read and write operations, various key-value stores, such as Cassandra, and Dynamo, offer only eventual consistency instead. One main motivation for such a decision is performance degradation when guaranteeing atomic consistency. In this paper, we use time with known bounded uncertainty to improve the performance of write operations, while maintaining atomic consistency. We show how to use the concept of commit wait in a shared memory register to perform a write operation in one phase (message round trip), instead of two. We evaluate the solution experimentally by comparing it to ABD, a well-known algorithm for achieving atomic consistency in an asynchronous network, which uses two phases for write operations. We also compare our protocol to an eventually consistent register. Our experiments show an improved throughput, and lower write latency, compared to the ABD algorithm.

  • 3.
    Haridi, Seif
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Arad, Cosmin
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Shafaat, Tallat
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Self-Distributing Software Updates through Epidemic Dissemination2010In: Proceedings - 2010 4th IEEE International Conference on Self-Adaptive and Self-Organizing Systems Workshop, SASOW 2010, 2010, p. 243-246Conference paper (Refereed)
    Abstract [en]

    Peer-to-peer systems have recently received tremendous amount of popularity in both research and commercial endeavors. This paper argues for the systematic exploration of a hybrid of centralized and peer-to-peer system design. We give an example application of peer-to-peer architecture to an inherently centralized service and show how this application raises an interesting research question in the field of epidemic information dissemination. We propose a previously unexplored push mechanism for the distribution of updates for system software that exists in millions of copies.

  • 4.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Ahmad, Bilal
    KTH.
    Haridi, Seif
    Swedish Institute of Computer Science.
    ID-replication for structured peer-to-peer systems2012In: Euro-Par 2012 Parallel Processing: 18th International Conference, Euro-Par 2012, Rhodes Island, Greece, August 27-31, 2012. Proceedings / [ed] Christos Kaklamanis, Theodore Papatheodorou, Paul G. Spirakis, Springer Berlin/Heidelberg, 2012, p. 364-376Conference paper (Refereed)
    Abstract [en]

    Structured overlay networks, like any distributed system, use replication to avoid losing data in the presence of failures. In this paper, we discuss the short-comings of existing replication schemes and propose a technique for replication, called ID-Replication. ID-Replication allows different replication degrees for keys in the system, thus allowing popular data to have more copies. We discuss how ID-Replication is less sensitive to churn compared to existing replication schemes, which makes ID-Replication better suited for building consistent services on top of overlays compared to other schemes. Furthermore, we show why ID-Replication is simpler to load-balance and more secure compared to successor-list replication. We evaluate our scheme in detail, and compare it with successor-list replication.

  • 5.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Baden, Scott B.
    A method of adaptive coarsening for compressing scientific datasets2007In: Applied Parallel Computing: State Of The Art In Scientific Computing / [ed] Kagstrom, B; Elmroth, E; Dongarra, J; Wasniewski, J, 2007, Vol. 4699, p. 774-780Conference paper (Refereed)
    Abstract [en]

    We present adaptive coarsening, a multi-resolution lossy compression algorithm for scientific datasets. The algorithm provides guaranteed error bounds according to the user's requirements for subsequent post-processing. We demonstrate compression factors of up to an order of magnitude with datasets coming from solutions to time-dependent partial differential equations in one and two dimensions.

  • 6.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Ghodsi, A.
    Haridi, S.
    Managing network partitions in structured P2P networks2010In: Handbook of Peer-to-Peer Networking, Springer, 2010, p. 1127-1147Chapter in book (Refereed)
    Abstract [en]

    Structured overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale distributed system is destined to face network partitions. Consequently, the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems. This makes it a crucial requirement for building any structured peer-to-peer systems to be resilient to network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of structured peer-to-peer systems. Structured overlays have mainly been studied under churn (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based structured overlay networks, which constitute the majority of the structured overlays, are intrinsically ill-suited for merging rings. In this chapter, we motivate the problem of network partitions and mergers in structured overlays. We discuss how a structured overlay can automatically detect a network partition and merger. We present an algorithm for merging multiple similar ring-based overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger, something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger, the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.

  • 7.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Ghodsi, Ali
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    A Practical Approach to Network Size Estimation for Structured Overlays2008In: SELF-ORGANIZING SYSTEMS, PROCEEDINGS / [ed] Hummel KA; Sterbenz JPG, Berlin: SPRINGER-VERLAG , 2008, Vol. 5343, p. 71-83Conference paper (Refereed)
    Abstract [en]

    Structured overlay networks have recently received much attention due to their self-* properties under dynamic and decentralized settings. The number of nodes in all overlay fluctuates all the time due to churn. Since knowledge of the size of the. overlay is a core requirement for many systems, estimating the size in a decentralized manner is a challenge taken up by recent research activities. Gossip-based Aggregation has been shown to give accurate estimates for the network size, but previous work done is highly sensitive to node failures. In this paper, we present a gossip-based aggregation-style network size estimation algorithm. We discuss shortcomings of existing aggregation-based size estimation algorithms, and give a solution that is highly robust to node failures and is adaptive to network delays. We examine our solution in various scenarios to demonstrate. its effectiveness.

  • 8.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Ghodsi, Ali
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Dealing with network partitions in structured overlay networks2009In: Peer-to-Peer Networking and Applications, ISSN 1936-6442, Vol. 2, no 4, p. 334-347Article in journal (Refereed)
    Abstract [en]

    Structured overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale distributed system is destined to face network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of structured peer-to-peer systems. These systems have mainly been studied under churn (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based structured overlay networks, which constitute the majority of the structured overlays, are intrinsically ill-suited for merging rings. In this paper, we present an algorithm for merging multiple similar ring-based overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger, something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger, the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.

  • 9.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Ghodsi, Ali
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Handling network partitions and mergers in structured overlay networks2007In: P2P: Seventh International Conference On Peer-To-Peer Computing, Proceedings / [ed] Hauswirth, M; Montresor, A; Shahmehri, N; Wehrle, K; Wierzbicki, A, 2007, p. 132-139Conference paper (Refereed)
    Abstract [en]

    Structured overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale. distributed system is destined to face network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of structured peer-to-peer systems. These systems have mainly been studied under chum (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based structured overlay networks, which constitute the majority of the structured overlays, are intrinsically ill-suited for merging rings. In this paper we present an algorithm for merging multiple similar ring-based overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.

  • 10.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Moser, Monika
    Ghodsi, Ali
    Schuett, Thorsten
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Reinefeld, Alexander
    On consistency of data in structured overlay networks2008In: GRID COMPUTING: ACHIEVEMENTS AND PROSPECTS / [ed] Gorlatch, S; Fragopoulou, P; Priol, T, NEW YORK: SPRINGER , 2008, p. 249-260Conference paper (Refereed)
    Abstract [en]

    Data consistency can be violated in Distributed Hash Tables (DHTs) due to inconsistent lookups. In this paper, we identify the events leading to inconsistent lookups and inconsistent responsibilities for a key. We find the inaccuracy of failure detectors as the main reason for inconsistencies. By simulations with inaccurate failure detectors, we study the probability of reaching a system configuration which may lead to inconsistent data. We analyze majority-based algorithms for operations on replicated data. To ensure that concurrent operations do not violate consistency, they have to use non-disjoint sets of replicas. We analytically derive the probability of concurrent operations including disjoint replica sets. By combining the simulation and analytical results, we show that the probability for a violation of data consistency is negligibly low for majority-based algorithms in DHTs.

  • 11.
    Shafaat, Tallat M.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Schütt, Thomas
    Moser, Monika
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Ghodsi, Ali
    Reinefeld, Alexander
    Key-based consistency and availability in structured Overlay Networks2008In: Proceedings of the 17th International Symposium on High Performance Distributed Computing 2008, HPDC'08, 2008, p. 235-236Conference paper (Refereed)
    Abstract [en]

    Structured Overlay Networks (SONs) provide a promising platform for high performance applications since they are scalable, fault-tolerant and self-managing. SONs provide lookup services that map keys to nodes that can be used as processing or storage resources. In SONs, lookups for a key may return inconsistent results. Consequently, it is difficult to provide consistent data services on top of SONs that build on key-based search. In this paper, we study the frequency of occurrence of inconsistent lookups. We show that the affect of lookup inconsistencies can be reduced by using node responsibilities. We present our results as a trade-off between consistency and availability of keys.

  • 12.
    Shafaat, Tallat Mahmood
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Dealing with Network Partitions and Mergers in Structured Overlay Networks2009Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.

  • 13.
    Shafaat, Tallat Mahmood
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Ghodsi, A.
    Haridi, S.
    Dealing with bootstrapping, maintenance, and network partitions and mergers in structured overlay networks2012In: Self-Adaptive and Self-Organizing Systems (SASO), 2012 IEEE Sixth International Conference on, IEEE , 2012, p. 149-158Conference paper (Refereed)
    Abstract [en]

    In the last decade, numerous structured overlay networks were proposed as a scalable infrastructure to build large-scale distributed systems under dynamic environments. These overlays were touted to be fault-tolerant and self-managing, yet, as we show in this paper, they fall short of handling some extreme scenarios they envision. These scenarios include bootstrapping, and underlying network partitions and mergers. We argue that handling such extreme scenarios is fundamental to providing a fault-tolerant and self-managing system, and thus, structured overlay networks should intrinsically be able to handle them. In this paper, we present ReCircle, an overlay algorithm that apart from performing periodic maintenance to handle churn like any other overlay, can merge multiple structured overlay networks. We show how such an algorithm can be used for decentralized bootstrapping. ReCircle does not have any extra cost during normal maintenance compared to an isolated overlay maintenance algorithm. Furthermore, the algorithm is tunable to tradeoff between bandwidth consumption and time to convergence during extreme events like bootstrapping and handling network partitions and mergers. We evaluate the algorithm extensively under various scenarios through simulation and experimentation on Planet Lab.

  • 14.
    Tallat Mahmood, Shafaat
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Partition Tolerance and Data Consistency in Structured Overlay Networks2013Doctoral thesis, monograph (Other academic)
    Abstract [en]

    Structured overlay networks form a major class of peer-to-peer systems, which are used to build scalable, fault-tolerant and self-managing distributed applications. This thesis presents algorithms for structured overlay networks, on the routing and data level, in the presence of network and node dynamism.

    On the routing level, we provide algorithms for maintaining the structure of the overlay, and handling extreme churn scenariossuch as bootstrapping, and network partitions and mergers. Since any long lived Internet-scale distributed system is destined to face network partitions, we believe structured overlays should intrinsically be able to handle partitions and mergers. In this thesis, we discuss mechanisms for detecting a network partition and merger, and provide algorithms for merging multiple ring-based overlays. Next, we present a decentralized algorithm for estimating the number of nodes in a peer-to-peer system. Lastly, we discussthe causes of routing anomalies (lookup inconsistencies), their effect on data consistency, and mechanisms on the routing level to reduce data inconsistency.

    On the data level, we provide algorithms for achieving strong consistency and partition tolerance in structured overlays. Based on our solutions on the routing and data level, we build a distributed key-value store for dynamic partially synchronous networks, which is linearizable, self-managing, elastic, and exhibits unlimited linear scalability. Finally, we present a replication scheme for structured overlays that is less sensitive to churn than existing schemes, and allows different replication degrees for different key ranges that enables using higher number of replicas for hotspots and critical data.

1 - 14 of 14
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