Browsing Journal Articles and Proceedings by Issue Date

Now showing items 1-20 of 67

    • Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication 

      Newport, Calvin Charles; Kuhn, Fabian; Lynch, Nancy Ann (Association for Computing Machinery, 2009)
      We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ...

    • Brief announcement: Minimum spanning trees and cone-based topology control 

      Cornejo Collado, Alex; Lynch, Nancy Ann (Association for Computing Machinery, 2009)
      Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains ...

    • On the weakest failure detector ever 

      Kuznetsov, Petr; Herlihy, Maurice; Newport, Calvin Charles; Lynch, Nancy Ann; Guerraoui, Rachid (Springer Berlin Heidelberg, 2009-01)
      Many problems in distributed computing are impossible to solve when no information about process failures is available. It is common to ask what information about failures is necessary and sufficient to circumvent some ...

    • Self-stabilizing robot formations over unreliable networks 

      Gilbert, Seth; Lynch, Nancy Ann; Mitra, Sayan; Nolte, Tina (Association for Computing Machinery, 2009-07)
      We describe how a set of mobile robots can arrange themselves on any specified curve on the plane in the presence of dynamic changes both in the underlying ad hoc network and in the set of participating robots. Our strategy ...

    • Simulating fixed virtual nodes for adapting wireline protocols to MANET 

      Wu, Jiang; Griffeth, Nancy; Droms, Ralph; Lynch, Nancy Ann; Newport, Calvin Charles (Institute of Electrical and Electronics Engineers, 2009-08)
      The virtual node layer (VNLayer) is a programming abstraction for mobile ad hoc networks (MANETs). It defines simple virtual servers at fixed locations in a network, addressing a central problem for MANETs, which is the ...

    • The abstract MAC layer 

      Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin Charles (Association for Computing Machinery, 2009-09)
      A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an Abstract MAC Layer. This service provides reliable local ...

    • Timeout Order Abstraction for Time-Parametric Verification of Loosely Synchronized Real-Time Distributed Systems 

      Umeno, Shinya; Lynch, Nancy Ann (Artist Consortium, 2009-12)
      We present timeout order abstraction (TO-abstraction), a technique to systematically abstract a given loosely synchronized real-time distributed system (LSRTDS) into an untimed model. We define the subclass of LSRTDS’s ...

    • Distributed computation in dynamic networks 

      Kuhn, Fabian; Lynch, Nancy Ann; Oshman, Rotem (Association for Computing Machinery, 2010)
      In this paper we investigate distributed computation in dynamic networks in which the network topology changes from round to round. We consider a worst-case model in which the communication links for each round are chosen ...

    • Neighbor discovery in mobile ad hoc networks using an abstract MAC layer 

      Viqar, Saira; Welch, Jennifer L.; Cornejo Collado, Alex; Lynch, Nancy Ann (Institute of Electrical and Electronics Engineers, 2010-01)
      We explore the problem of neighbor discovery in a mobile ad hoc network environment. We describe a protocol for learning about neighboring nodes in such an environment. The protocol is used for establishing and tearing ...

    • Broadcasting in unreliable radio networks 

      Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin Charles; Oshman, Rotem; Richa, Andrea (Association for Computing Machinery, 2010-07)
      Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set ...

    • Rambo: a robust, reconfigurable atomic memory service for dynamic networks 

      Gilbert, Seth; Lynch, Nancy Ann; Shvartsman, Alexander A. (Springer-Verlag, 2010-09)
      n this paper, we present Rambo, an algorithm for emulating a read/write distributed shared memory in a dynamic, rapidly changing environment. Rambo provides a highly reliable, highly available service, even as participants ...

    • Decomposing broadcast algorithms using abstract mac layers 

      Khabbazian, Majid; Kowalski, Dariusz R.; Kuhn, Fabian; Lynch, Nancy Ann (Association for Computing Machinery, 2010-09)
      In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, ...

    • Automated Formal Verification of the DHCP Failover Protocol Using Timeout Order Abstraction 

      Umeno, Shinya; Lynch, Nancy Ann (Institute of Electrical and Electronics Engineers (IEEE), 2010-11)
      In this paper, we present automated formal verification of the DHCP Failover protocol. We conduct bounded model-checking for the protocol using Timeout Order Abstraction (TO-Abstraction), a technique to abstract a given ...

    • Reliably Detecting Connectivity Using Local Graph Traits 

      Cornejo Collado, Alex; Lynch, Nancy Ann (Springer, 2010-12)
      Local distributed algorithms can only gather sufficient information to identify local graph traits, that is, properties that hold within the local neighborhood of each node. However, it is frequently the case that global ...

    • Structuring Unreliable Radio Networks 

      Censor-Hillel, Keren; Lynch, Nancy Ann; Newport, Calvin Charles (Association for Computing Machinery (ACM), 2011)
      In this paper we study the problem of building a connected dominating set with constant degree (CCDS) in the dual graph radio network model [4,9,10]. This model includes two types of links: reliable, which always deliver ...

    • Brief Announcement: Partial Reversal Acyclicity 

      Radeva, Tsvetomira; Lynch, Nancy Ann (Association for Computing Machinery (ACM), 2011)
      Partial Reversal (PR) is a link reversal algorithm which ensures that an initially directed acyclic graph (DAG) is eventually a destination-oriented DAG. While proofs exist to establish the acyclicity property of PR, they ...

    • The abstract MAC layer 

      Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin Charles (Springer Nature America, Inc, 2011)
      A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local ...

    • The abstract MAC layer 

      Kuhn, Fabian; Lynch, Nancy; Newport, Calvin (Springer Nature America, Inc, 2011)
      A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local ...

    • MAC Design for Analog Network Coding 

      Khabbazian, Majid; Kuhn, Fabian; Lynch, Nancy Ann; Medard, Muriel; Parandehgheibi, Ali (Association for Computing Machinery (ACM), 2011-06)
      Most medium access control (MAC) mechanisms discard collided packets and consider interference harmful. Recent work on Analog Network Coding (ANC) suggests a different approach, in which multiple interfering transmissions ...

    • Modeling radio networks 

      Newport, Calvin Charles; Lynch, Nancy Ann (Springer Science and Business Media LLC, 2011-07-06)
      We describe a modeling framework and collection of foundational composition results for the study of probabilistic distributed algorithms in synchronous radio networks. Though the radio setting has been studied extensively ...