Works of Nancy Lynch: Recent submissions

Now showing items 73-75 of 99

    • The Cost of Global Broadcast Using Abstract MAC Layers 

      Lynch, Nancy; Kuhn, Fabian; Kowalski, Dariusz; Khabbazian, Majid (2010-02-09)
      We analyze greedy algorithms for broadcasting messages throughout a multi-hop wireless network, using a slot-based model that includes message collisions without collision detection. Our algorithms are split formally into ...

    • 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 ...

    • 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, ...