2017

P. Flocchini, G. Prencipe, N. Santoro, G. Viglietta
Distributed computing by mobile robots: Uniform circle formation.
Distributed Computing to appear, 2017 (pdf)


G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, G. Viglietta
Mutual visibility by luminous robots without collisions.
Information and Computation, 254(3), 392-418, 2017 (pdf)


S. Dobrev, R. Kralovic, N. Santoro
On the cost of waking up.
International Journal of Networking and Computing, 7(2), 336-348, 2017 (pdf)


N. Santoro

A MICROSCOPIC VIEW OF TIME AND MESSAGES

(Book Chapter of) : Emergent Computation

A. Adamatzky (Ed.), Springer 2017. (preliminary version - pdf)


G.A. Di Luna, P. Flocchini, N. Santoro, G. Viglietta, M. Yamashita
Meeting in a polygon by anonymous oblivious robots.
31st International Symposium on Distributed Computing (DISC), to appear, 2017 (pdf)


G.A. Di Luna, P. Flocchini, N. Santoro, G. Viglietta, Y. Yamauchi
Brief Announcement: Shape formation by programmable particles.
31st International Symposium on Distributed Computing (DISC), to appear, 2017 (pdf)


G.A. Di Luna, P. Flocchini, T. Izumi, T. Izumi, N. Santoro, G. Viglietta
On the power of weaker pairwise interaction: Fault-tolerant simulation of population protocols.
37th IEEE International Conference on Distributed Computing Systems (ICDCS), to appear, 2017 (pdf)


G.A. Di Luna, P. Flocchini, G. Prencipe, L. Pagli, N. Santoro, G. Viglietta
Gathering in dynamic rings.
24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), to appear, 2017 (pdf)


G.A. Di Luna, P. Flocchini, T. Izumi, T. Izumi, N. Santoro, G. Viglietta
Population protocols with faulty interactions: The impact of a leader.
10th International Conference on Algorithms and Complexity (CIAC), to appear, 2017 (pdf)


S. Das, G.A. Di Luna, P. Flocchini, N. Santoro, G. Viglietta
Mediated population protocols: Leader election and applications.
14th Conference on Theory and Applications of Models of Computation (TAMC), to appear, 2017 (pdf)




2016

P. Flocchini, N. Santoro, G. Viglietta, M. Yamashita
Rendezvous with constant memory.
Theoretical Computer Science, 621: 57-72, 2016 (pdf)


P. Flocchini, F. Luccio, L. Pagli, N. Santoro,
Network decontamination under m-immunity
Discrete Applied Mathematics
201: 114-129, 2016 (pdf)


S. Das, P. Flocchini, G. Prencipe, N. Santoro, M. Yamashita
Autonomous mobile robots with lights.
Theoretical Computer Science, 609: 171-184, 2016 (pdf)


B. Balamohan, S. Dobrev, P. Flocchini, N. Santoro
Exploring an unknown dangerous graph with a constant number of tokens.
Theoretical Computer Science, 610: 169-181, 2016 (pdf)

G.A. Di Luna, S. Dobrev, P. Flocchini, N. Santoro
Live exploration of dynamic rings.
36th IEEE International Conference on Distributed Computing Systems (ICDCS), 570-579, 2016 (pdf)


P. Flocchini, N. Santoro, G. Viglietta M. Yamashita.
Universal systems of oblivious mobile robots.
23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO) , 242-257, 2016 (pdf)


S. Dobrev, R. Kralovic, N. Santoro
On the complexity of distributed wake up.
8th International Workshop on Parallel and Distributed Algorithms and Applications (PDAA), to appear, 2016 (extended version)


G.A. Di Luna, P. Flocchini, G. Prencipe, N. Santoro, G. Viglietta
A rupestrian algorithm.
8th International Conference on Fun with Algorithms (FUN), LIPICS Vol. 49, 2016 (pdf)




2015

N. Santoro,
Time to change: On distributed computing in dynamic networks. (invited paper)
19th International Conference on Principles of Distributed Systems (OPODIS) to appear, 2015 (pdf)


A. Casteigts, P. Flocchini, E. Godard, N. Santoro, M. Yamashita
On the expressivity of time-varying graphs.
Theoretical Computer Science, 590: 27-37, 2015 (pdf)


S. Das, P. Flocchini, N. Santoro, M. Yamashita
Forming sequences of geometric patterns with oblivious mobile robots.
Distributed Computing, 28(2): 131-145, 2015 (pdf)


A. Casteigts, P. Flocchini, B. Mans, N. Santoro
Shortest, fastest, and foremost broadcast in dynamic networks.
International Journal of Foundations of Computer Science, 26(4): 499-522, 2015. (pdf)


J. Cai, P. Flocchini, N. Santoro
Distributed black virus decontamination and rooted acyclic orientations.
13th IEEE International Conference on Dependable, Autonomic and Secure Computing (DASC), to appear, 2015 (pdf)


J. Cai, P. Flocchini, N. Santoro
Black virus decontamination in arbitrary networks.
3rd Conference on Information Systems and Technologies, Advances in Intelligent Systems and Computing 353, Springer, 991-1000, 2015 (pdf)




2014

N. Santoro, E. Velazquez

ENERGY RESTORATION IN MOBILE SENSOR NETWORKS

(Book Chapter of) : Wireless Sensor and Robot Networks

N. Mitton, D. Simplot-Ryl (Eds.), World Scientific 2014. (pdf)


A. Casteigts, P. Flocchini, B. Mans, N. Santoro
Measuring temporal lags in delay-tolerant networks.
IEEE Transactions on Computers, 63(2): 397-410, 2014 (pdf)


J. Cai, P. Flocchini, N. Santoro
Decontaminating a network from a black virus.
International Journal of Networking and Computing, 4(1): 151-173, 2014 (pdf)


P. Flocchini, G. Prencipe, N. Santoro, G. Viglietta
Solving the uniform circle formation problem.
18th International Conference on Principles of Distributed Systems (OPODIS), 113-124, 2014 (extended version)


E.Mesa-Barrameda, N. Santoro, W. Shi, N. Taleb
Sensor deployment by a robot in an unknown orthogonal region: Achieving full coverage
IEEE International Workshop on Parallel and Distributed Computing in Geoinformation and Remote Sensing (PDGRS-ICPADS), 951-961, 2014 (pdf)


S. Das, P. Flocchini, G. Prencipe, N. Santoro
Synchronized dancing of oblivious chameleons.
7th International Conference on Fun with Algorithms (FUN), 113-124, 2014 (pdf)


M.H. Hesari, P. Flocchini, L. Narayanan, J. Opatrny, N. Santoro
Distributed barrier coverage with relocatable sensors.
21st International Colloquium on Structural Information and Communication Complexity (SIROCCO), 235-249, 2014 (pdf)


G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, N. Santoro, G. Viglietta
Robots with lights: Overcoming obstructed visibility without colliding.
16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2014 (pdf)


G.A. Di Luna, P. Flocchini, F. Poloni, N. Santoro, G. Viglietta
The mutual visibility problem for oblivious robots.
26th Canadian Conference on Computational Geometry (CCCG), 2014 (pdf)




2013

P. Flocchini, B. Mans, N. Santoro
On the exploration of time-varying networks.
Theoretical Computer Science, 469: 53-68, 2013. (pdf)


P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro,
Computing without communicating: Ring exploration by asynchronous oblivious robots.
Algorithmica
, 65(3): 562-583, 2013. (pdf)


S. Dobrev, P. Flocchini, R. Kralovic, N. Santoro
Exploring an unknown dangerous graph using tokens.
Theoretical Computer Science, 472: 28-45, 2013.


A. Casteigts, P. Flocchini, E. Godard, N. Santoro, M. Yamashita
Expressivity of time-varying graphs.
19th International Symposium on Fundamentals of Computation Theory (FCT), 95-106, 2013. (extended version)


G. Viglietta, P. Flocchini, N. Santoro, M. Yamashita
Rendezvous of two robots with constant memory.
20th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), 189-200, 2013. (extended version)


S. Das, E. Mesa, N. Santoro
Uniform dispersal of asynchronous finite-state mobile robots in presence of holes.
9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), 228-243, 2013. (pdf)


J. Cai, P. Flocchini, N. Santoro,
Network decontamination from a black virus
15th Work. on Advances in Parallel and Distributed Computational Models (APDCM)
696-705, 2013. (extended version)


P. Flocchini, F. Luccio, L. Pagli, N. Santoro,
Optimal network decontamination with threshold immunity
8th International Conference on Algorithms and Complexity (CIAC)
234-245, 2013. (extended version)


N. Santoro,
Mobility and computations: Open research directions (invited paper)
7th International Workshop on Algorithms and Computation (WALCOM) 1-3, 2013.




2012

P. Flocchini, G. Prencipe, N. Santoro

DISTRIBUTED COMPUTING BY OBLIVIOUS MOBILE ROBOTS

Morgan & Claypool, 2012.


L. Barriere, P. Flocchini, F. V. Fomin, P. Fraigniaud, N. Nisse, N. Santoro, D. Thilikos
Connected graph searching
Information and Computation, 219: 1-16, 2012. (pdf)


M. Cielibak, P. Flocchini, G. Prencipe, N. Santoro
Distributed computing by mobile robots: Gathering.
SIAM Journal on Computing, 41(4): 829-879, 2012. (pdf)


P. Flocchini, D. Ilcinkas, N. Santoro
Ping pong in dangerous graphs: optimal black hole search with pebbles.
Algorithmica, 62(3-4): 1006-1033, 2012. (pdf)


P. Flocchini, M. Kellett, P. Mason, N. Santoro,
Searching for black holes in subways
Theory of Computing Systems, 50(1): 158-184, 2012. (pdf)


P. Flocchini, T. Mesa, L. Pagli, G. Prencipe, N. Santoro,
Distributed minimum spanning tree maintenance for transient node failures
IEEE Transactions on Computers,61(3): 408-414, 2012. (pdf)


A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro
Time-varying graphs and dynamic networks.
International Journal of Parallel, Emergent and Distributed Systems, 27: 346-359, 2012. (pdf)


P. Flocchini, N. Santoro

DISTRIBUTED SECURITY ALGORITMS FOR MOBILE AGENTS

(Book Chapter of) :
Mobile Agents in Networking and Distributed Computing

J. Cao, S. Das (Eds.), Wiley 2012. (preliminary version - pdf)


S. Das, P. Flocchini, G. Prencipe, N. Santoro, M. Yamashita
The power of Lights: Synchronizing asynchronous robots using visible bits.
32nd International Conference on Distributed Computing Systems (ICDCS), 2012. (pdf)


B. Balamohan, S. Dobrev, P. Flocchini, N. Santoro
Asynchronous exploration of an unknown anonymous dangerous graph with O(1) pebbles.
19th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), 279-290, 2012. (extended version)


P. Flocchini, M. Kellett, P. Mason, N. Santoro
Finding good coffee in Paris.
6th International Conference on Fun with Algorithms (FUN), 54-165, 2012. (pdf)


P. Flocchini, M. Kellett, P. Mason, N. Santoro
Fault-tolerant exploration of an unknown dangerous graph by scattered agents.
14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2012. (pdf)




2011

P. Flocchini, G. Prencipe, N. Santoro

COMPUTING BY MOBILE ROBOTIC SENSORS

(Book Chapter of) :
Theoretical Aspects of Distributed Computing in Sensor Networks

S. Nikoletseas, J. Rolim (Eds.), Springer 2011. (preliminary version - pdf)


M. Duckham, D. Nussbaum, J.-R. Sack, N. Santoro,
Efficient decentralized computation of the topology of spatial regions
IEEE Transactions on Computers, 60(8): 1100-1113, 2011. (pdf)


X. Li, H. Frey, N. Santoro, I. Stojmenovic
Strictly localized sensor self-deployment for optimal focused coverage
IEEE Transactions on Mobile Computing, 10(11): 1520-1533, 2011. (pdf)


P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro,
How many oblivious robots can explore a line.
Information Processing Letters
, 111(20): 1027-1031, 2011. (pdf)


B. Gfeller, N. Santoro, and P. Widmayer
A distributed algorithm for finding all best swap edges of a minimum diameter spanning tree.
IEEE Transactions on Dependable and Secure Computing, 8(1): 1-12, 2011. (pdf)


L. Barriere, P. Flocchini, E. Mesa-Barrameda, N. Santoro,
Uniform scattering of autonomous mobile robots in a grid
Int. Journal of Foundations of Computer Science, 22(3): 679-697, 2011. (pdf)


B. Balamohan, P. Flocchini, A. Miri, N. Santoro
Time optimal algorithms for black hole search in rings.
Discrete Mathematics, Algorithms and Applications, 3(4): 1-15, 2011. (pdf)


A.-R. Mawlood-Yunis, M. Weiss, N. Santoro
A reference model for semantic peer-to-peer networks.
Journal of Data Semantics, 15: 37-65, 2011. (pdf)


A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro
Time-varying graphs and dynamic networks.
10th International Conference on Adhoc Networks and Wireless (ADHOC-NOW), 346-359, 2011. (pdf)


A. Casteigts, P. Flocchini, B. Mans, N. Santoro
Measuring temporal lags in delay-tolerant networks.
25th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2011. (pdf)


B. Balamohan, P. Flocchini, A. Miri, N. Santoro
Improving the optimal bounds for black hole search in rings.
18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 198-209, 2011. (extended version)


F. Amblard, A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro
On the temporal analysis of scientific network evolution.
3rd International Conference on Computational Aspects of Social Networks (CASON), 2011.


N. Santoro, W. Quattrociocchi, P. Flocchini, A. Casteigts, F. Amblard
Time-varying graphs and social network analysis: Temporal indicators and metrics.
3rd AISB Social Networks and Multiagent Systems Symposium (SNAMAS) , 32-38, 2011.


E. Velazquez, N. Santoro
Neighbour selection and sensor knowledge: Proactive approach for the frugal feeding problem in wireless sensor networks.
3rd International Conference on Ad Hoc Networks (ADHOCNETS), 2011.




2010

P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro
Remembering without memory: Tree exploration by asynchronous oblivious robots.
Theoretical Computer Science, 411 (14-15): 1583-1598, 2010. (pdf)


A.-R. Mawlood-Yunis, M. Weiss, N. Santoro
From P2P to reliable semantic P2P systems.
Peer-to-Peer Networking and Applications, 3 (4), 363-, 2010. (pdf)


D. Nussbaum, N. Santoro
On the message complexity of global computations.
14th International Conference on Principles of Distributed Systems (OPODIS), 427-442, 2010.


S. Das, P. Flocchini, N. Santoro, M. Yamashita
On the computational power of oblivious robots: forming a series of geometric patterns.
29th ACM Symposium on Principles of Distributed Computing (PODC), 2010. (extended version)


J. Chalopin, P. Flocchini, B. Mans and N. Santoro
Network exploration by silent and oblivious robots.
36th International Workshop on Graph Theoretic Concepts in Computer Science (WG), 2010.


B. Balamohan, P. Flocchini, A. Miri, N. Santoro
Time optimal algorithms for black hole search in rings.
4th International Conference on Combinatorial Optimization and Applications (COCOA), 58-71, 2010. (pdf)


A. Casteigts, P. Flocchini, B. Mans, N. Santoro
Deterministic computations in time-varying graphs: broadcasting under unstructured mobility.
6th IFIP International Conference on Theoretical Computer Science (TCS), 2010. (pdf)


E. Velazquez, N. Santoro
Mobility-based strategies for energy restoration in wireless sensor networks.
6th International Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2010. (pdf)


P. Flocchini, M. Kellett, P. Mason, N. Santoro,
Mapping an unfriendly subway system
International Conference on Fun with Algorithms (FUN), 190-201, 2010. (pdf)


E. Velazquez, N. Santoro
Efficient robot-based energy maintenance in wireless sensor networks.
5th IEEE International Symposium on Wireless Pervasive Computing, 2010. (pdf)


E. Velazquez, N. Santoro, Mark Lanthier
Pro-active strategies for the frugal feeding problem in wireless sensor networks.
The 2nd International ICST Conference on Sensor Systems and Software, 2010. (pdf)




2009

T. F. Abdelzaher, M. Raynal, and N. Santoro (Eds.),

PRINCIPLES OF DISTRIBUTED SYSTEMS

Springer, 2009.


A.-R. Mawlood-Yunis, M. Weiss, N. Santoro
FAULT-TOLERANT EMERGENT SEMANTICS IN P2P NETWORKS
(Book Chapter of) : Semantic Web Engineering
J. Cardoso, M. Lytras (Eds.), IGI 2009.


X. Li, N. Santoro, I. Stojmenovic
Localized distance-sensitive service discovery in wireless sensor and actor networks
IEEE Transactions on Computers, 58 (9), 1275-1288, 2009. (pdf)


P. Flocchini, A. Pelc, N. Santoro
Fault-tolerant sequential scan
Theory of Computing Systems
, 45 (1), 1-26, 2009. (pdf)


P. Flocchini, B. Mans, and N. Santoro
Exploration of periodically varying graphs
20th International Symposium on Algorithms and Computation (ISAAC), 2009.
Extended version (pdf)


X. Li, H. Frey, N. Santoro, I. Stojmenovic
Focused coverage by mobile sensor networks
6th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), 2009. (pdf)


P. Flocchini, M. Kellett, P. Mason, N. Santoro,
Map construction and exploration by mobile agents scattered in a dangerous network
IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2009. (pdf)


L. Barriere, P. Flocchini, E. Mesa-Barrameda, N. Santoro,
Uniform scattering of autonomous mobile robots in a grid
11th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), 2009.


H. Frey, X. Li, N. Santoro, I. Stojmenovic,
Localized sensor self-deployment for guaranteed coverage radius maximization
IEEE International Conference on Communications
, 2009.


E. Velazquez, N. Santoro
Distributed facility location for sensor network maintenance.
5th International Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2009.


A.-R. Mawlood-Yunis, M. Weiss, N. Santoro
Reference model for semantic peer- to-peer networks
14th International Conference on e-Technologies, 2009.




2008

N. Santoro, P. Widmayer

DISTRIBUTED COMPUTING IN PRESENCE OF MOBILE FAULTS

(Book Chapter of) : Handbook of Parallel Computing

S. Rajasekaran, J. Reif (Eds.), Chapman & Hall/CRC 2008.
(preliminary version - pdf)


P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer
Arbitrary pattern formation by asynchronous oblivious robots
Theoretical Computer Science
407 (1-3), 412-447, 2008. (pdf)


P. Flocchini. G. Prencipe, N. Santoro,
Self-deployment of mobile sensors on a ring
Theoretical Computer Science
402 (1), 67-80, 2008. (pdf)


S. Dobrev, R. Kralovic, R. Kralovic, N. Santoro,
On fractional dynamic faults with threshold
Theoretical Computer Science
399 (1-2), 101-117, 2008. (pdf)


P. Flocchini, L. Pagli, G. Prencipe, N. Santoro, P. Widmayer
Computing all the best swap edges distributively
Journal of Parallel and Distributed Computing
68 (7), 976-983, 2008. (pdf)


S. Dobrev, N. Santoro, W. Shi,
Using scattered mobile agents to locate a black hole in a unoriented ring with tokens
Int. Journal of Foundations of Computer Science
19 (6), 1355-1372, 2008.


P. Flocchini, D. Ilcinkas, N. Santoro,
Ping-pong in dangerous graphs
Proc. 22nd International Symposium on Distributed Computing (DISC)
, 227-241, 2008.


P. Flocchini, B. Mans, N. Santoro,
Tree decontamination with temporary immunity
Proc. 19th International Symposium on Algorithms and Computation (ISAAC)
, 330-341, 2008.


P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro,
Remembering without memory: Tree exploration by asynchronous oblivious robots
Proc. 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO)
, 33-47, 2008. (pdf)


E. Mesa Barrameda, S. Das N. Santoro,
Deployment of asynchronous robotic sensors in unknown orthogonal environments
Proc. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSOR)
, 125-140, 2008. (pdf)


X. Li, K. Lu, N. Santoro, I. Simplot-RyI. Stojmenovic
Alternative data gathering schemes for wireless sensor networks
Proc. International Workshop on Ordered sets and Graphs: Interaction with Computer Science (ROGICS)
, 577--586, 2008.


X. Li, N. Santoro, I. Stojmenovic
Localized distance-sensitive service discovery in wireless sensor networks
Proc. 1st ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC)
, 85-92, 2008.




2007

N. Santoro,

DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS

Wiley 2007.


S. Das, P. Flocchini, S. Kutten, A. Nayak, N. Santoro,
Map construction of unknown graphs by multiple agents
Theoretical Computer Science
385 (1-3): 34-48, 2007. (pdf)


L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro,
Election and rendezvous in fully anonymous networks with sense of direction
Theory of Computing Systems
40 (2): 143-162, 2007. (pdf)


S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro,
Mobile search for a black hole in an anonymous ring
Algorithmica
48: 67--90, 2007. (pdf)


N. Santoro, P. Widmayer,
Agreement in synchronous networks with ubiquitous faults
Theoretical Computer Science
384: 232-249, 2007. (pdf)


F. Luccio, L. Pagli, N. Santoro,
Network decontamination in presence of local immunity
Int. Journal of Foundations of Computer Science
18 (3): 457-- 474, 2007. (pdf)


M. H. Albert, M.D. Atkinson, D. Nussbaum, J.-R. Sack, N. Santoro,
On the longest increasing subsequence of a circular list
Information Processing Letters
101: 55-59, 2007. (pdf)


P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro
Computing without communicating: Ring exploration by asynchronous oblivious robots
11th Symposium on Principles of Distributed Systems} (OPODIS 2007)
, 105-118, 2007. (pdf)


J. Chalopin, S. Das, N. Santoro,
Rendezvous of mobile agents in unknown graphs with faulty links
Proc. 21st International Conference on Distributed Computing (DISC'07)
, 108-122, 2007. (pdf)


B. Gfeller, N. Santoro, P. Widmayer,
A distributed algorithm for all best swap edges of a minimum diameter spanning tree
Proc. 21st International Conference on Distributed Computing (DISC'07)
, 268-282, 2007.
Extended version (pdf)


S. Das, P. Flocchini, N. Santoro, M. Yamashita,
Fault-tolerant simulation of message-passing algorithms by mobile agents
Proc. 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO'07)
, 289-303, 2007. (pdf)


P. Flocchini, T. Mesa, L. Pagli, G. Prencipe, N. Santoro,
Distributed computation of all node replacements of a minimum spanning tree
Proc. 13th International European Conference on Parallel and Distributed Computing (EuroPar'07)
, 598-607, 2007. (pdf)


P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro
Exploration d'arbres par des equipes de robots asynchrones et sans memoire
9th Rencontres Francophones sur les Aspects Algorithmiques des Telécommunications} (AlgoTel 2007)
, 99-102, 2007. (pdf)


S. Dobrev, N. Santoro, W. Shi,
Scattered black hole search in an oriented ring using tokens
Proc. 13th International European Conference on Parallel and Distributed Computing (EuroPar'07)
, 608-617, 2007. (pdf)


X. Li, N. Santoro, I. Stojmenovic,
Mesh-based sensor relocation for coverage maintenance in mobile sensor networks
Proc. 4th International Conference on Ubiquitous Intelligence and Computing (UIC'07)
, 696-708, 2007. (pdf)


S. Dobrev, N. Santoro, W. Shi,
Locating a black hole in an unoriented ring using tokens
Proc. 9th Workshop on Advances in Parallel and Distributed Computational Models
, 1-8, 2007.




2006

S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro,
Searching for a black hole in arbitrary networks: optimal mobile agents protocols
Distributed Computing
19 (1): 1-19, 2006. (pdf)


S. Dobrev, P. Flocchini, R. Kralovic, G. Prencipe, P. Ruzicka, N. Santoro,
Black hole search in common interconnection networks
Networks
47 (2): 61-71, 2006. (pdf)


P. Flocchini, A. Mesa, L. Pagli, G. Prencipe, N. Santoro,
Point-of-failures shortest path rerouting: computing the optimal swaps distributively
IEICE Transactions Transactions on Information and Systems
E89-D (2): 700-708, 2006. (pdf)


J. Chalopin, S. Das, N. Santoro,
Groupings and pairings in anonymous networks
Proc. 20th International Conference on Distributed Computing (DISC'06)
105-119, 2006.


S. Das, P. Flocchini, A. Nayak, N. Santoro,
Effective elections for anonymous mobile agents
Proc. of 17th International Symposium on Algorithms and Computation (ISAAC'06), 732-743, 2006. (pdf)


P. Flocchini, N. Santoro,
Distributed security algorithms for mobile agents (invited paper)
Proc. of 8th Int. Conference on Distributed Computing and Networking (ICDCN'06), 1-14, 2006. extended version (pdf)


X. Li, N. Santoro,
An integrated self-deployment and coverage maintenance scheme for mobile sensors networks
Proc of 2nd Int. Conf. on Mobile Ad-Hoc and Sensors Networks (MSN), 2006. (pdf)


G. Prencipe, N. Santoro,
Distributed algorithms for mobile robots (invited paper)
Proc. of 5th IFIP International Conference on Theoretical Computer Science (TCS), 47-62, 2006. (pdf)


S. Dobrev, R. Kralovic, R. Kralovic, N. Santoro,
On fractional dynamic faults with threshold
Proc. 13th Colloquium on Structural Information and Communication Complexity (SIROCCO), 197-211, 2006.
Extended version (pdf)


S. Dobrev, P. Flocchini, N. Santoro,
Cycling through a dangerous network: A simple efficient strategy for black hole search
Proc. 26th International Conference on. Distributed Computing Systems (ICDCS'06), 57- , 2006. (pdf)


S. Dobrev, R. Kralovic, N. Santoro, W. Shi,
Black hole search in asynchronous rings using tokens
Proc. 6th Conference on Algorithms and Complexity (CIAC'06), 139-150, 2006. (pdf)


P. Flocchini. G. Prencipe, N. Santoro,
Self-deployment algorithms for mobile sensors on a ring
Proc. 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 59-70, 2006.
Extended version (pdf)


S. Dobrev, P. Flocchini, R. Kralovic, N. Santoro,
Exploring a dangerous unknown graph using tokens
Proc. of 5th IFIP International Conference on Theoretical Computer Science (TCS), 2006. (pdf)


F. Luccio, L. Pagli, N. Santoro,
Network decontamination with local immunization
Proc. of 8th Workshop on Advances in Parallel and Distributed Computational Models, 2006.
Extended version (pdf)


X. Li, N. Santoro,
ZONER: A zone-based sensor relocation protocol for mobile sensor networks
Proc 6th IEEE Workshop on Wireless Local Networks (WLN), 847-860, 2006. (pdf)


G. Coucopulos, N. Goel, A. Nayak, N. Santoro
Order and balance in continuously fault-tolerant distributions of objects
Proc. Int. Conf. on Parallel and Distributed Computing and Networks, 198-203, 2006.


F. Ahmad, N. Santoro, A. Nayak, N. Goel, A,R. Patnaik, A. Srivastava
Solving distributed mutual exclusion using cooperating mobile agents
Proc. 5th IEEE/ACIS International Conference on Computer and Information Science (ICIS), 458-463, 2006.


A-R. Mawlood-Yunis, M. Weiss, N. Santoro,
Issues for robust consensus building in P2P networks
Proc. of International Workshop on Ontology Content and Evaluation, 1021-1027, 2006.


A-R. Mawlood-Yunis, M. Weiss, N. Santoro,
Fault Classification in P2P semantic mapping
Proc. of IJCAI Workshop on Semantic Web for Collaborative Knowledge Acquisition, 2006.




2005



P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,
Gathering of robots with limited visibility
Theoretical Computer Science, 337 (1-3), 147-168, 2005. (pdf)


S. Das, P. Flocchini, A. Nayak, N. Santoro,
Exploration and labelling of an unknown graph by multiple agents
Proc. of 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO'05), 2005.
Extended version (pdf)


N. Santoro, P. Widmayer,
Majority and unanimity in synchronous networks with ubiquitous dynamic faults
Proc. of 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO'05), 2005.
Extended version (pdf)


N. Santoro,
Mobile agents computing: Security Issues and algorithmic solutions (invited paper)
Proc. of 9th EATCS Italian Conference on Theoretical Computer science (ITCS'05), 2005.




2004



E. Lodi, L. Pagli, N. Santoro (Eds),

Special Issue on Fun with Algorithms

Discrete Applied Mathematics 2004.


P. Flocchini, E. Lodi, F. Luccio, L. Pagli, N. Santoro.
Dynamic monopolies in tori
Discrete Applied Mathematics, 137, 197-212, 2004. (ps)


P. Flocchini, E. Kranakis, D. Krizank, F.L. Luccio, N. Santoro.
Sorting and Election in anonymous asynchronous rings
Journal of Parallel and Distributed Computing, 64:2, 254-265, 2004.


P. Flocchini, L. Pagli, G. Prencipe, N. Santoro, P. Widmayer, P. Zuva
Computing all the best swap edges distributively
Proc. of Symposium on Principles of Distributed Systems (OPODIS'04), 2004.
Extended version (pdf)


P. Flocchini, E. Kranakis, D. Krizanc, F.L. Luccio, N. Santoro, C. Sawchuk.
Mobile agents rendezvous when tokens fail
Proc. 11th International Colloquium on Structural Information and Communication Complexity (Sirocco'04), LNCS 3104, 161 - 172, 2004. (pdf)


P. Flocchini, T. Mesa, L. Pagli, G. Prencipe, N. Santoro .
Efficient protocols for computing optimal swap edges
Proc. of 3rd IFIP International Conference of Theoretical Computer Science (TCS 2004), 2004.
Extended version (pdf)


P. Flocchini, E. Kranakis, D. Krizanc, F.L. Luccio, N. Santoro, C. Sawchuk.
Multiple mobile agent rendezvous in a ring
Proc. 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), LNCS 2976, 599 - 608, 2004. (ps)


S. Dobrev, P. Flocchini, N. Santoro.
Improved bounds for optimal black hole search with a network map
Proc. 11th International Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS 3104, 111 - 122, 2004. (pdf)


A. Mawlood-Yunis, A. Nayak, D. Nussbaum, N. Santoro.
Comparing performance of two mobile agent platforms in distributed search
Proc. IEEE/ACM International Conference on Intelligent Agent Technology (IAT'04), 425-429, 2004. (pdf)




2003



S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro.
Multiple Agents RendezVous In a Ring in Spite of a Black Hole
Proc. of 7th International Conference on Principles of Distributed Systems (OPODIS), LNCS 3144, 34 - 46, 2003. (pdf)


M. Cielibak, P. Flocchini, G. Prencipe, N. Santoro.
Solving the robots gathering problem
Proc. of 30th International Colloquium on Automata, Languages and Programming (ICALP'03), LNCS 2719, 1181 - 1196, 2003. (pdf)


L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro.
Can we elect if we cannot compare ?
Proc. of 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA'03), 2003. (pdf)


E. Kranakis, D. Krizanc, N. Santoro, C. Sawchuk.
Mobile agent rendezvous in a ring
Proc. of 23rd IEEE Int. Conference on Distributed Computing Systems (ICDCS'03), 2003.
Extended version (pdf)


L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro.
Rendez-vous and election in anonymous networks with sense of direction
Proc. of 10th Colloquium on Structural Information and Communcation Complexity (SIROCCO'03), 2003.
Extended version (pdf)


L. Barriere, P. Fraigniaud, D. Thilikos, N. Santoro.
Searching is not jumping
Proc. of 29th Workshop on Graph Theoretic Concepts in Computer Science (WG'03), LNCS 2880, 34-45, 2003.
Extended version: Connected and Internal graph searching (ps)


N. Santoro.
Distributed computations by autonomous mobile robots {invited paper)
Proc. of 28th Conference onTheory and Practice of Informatics (SOFSEM'03), LNCS 2234, 110, 2003.


P. Flocchini, A. Roncato, N. Santoro,
Backward consistency and sense of direction in advanced distributed systems
SIAM J. on Computing 32:2, 281-306, 2003. (ps)


P. Flocchini, B. Mans, N. Santoro,
Sense of direction in distributed computing
Theoretical Computer Science 291:1, 29-53, 2003. (pdf)


P. Flocchini, A. Roncato, N. Santoro,
Computing in anonymous networks with sense of direction
Theoretical Computer Science 301, 355-379, 2003. (pdf)


U.-M. O'Reilly, N. Santoro,
Tight bound for synchronous communication of information using bits and silence
Discrete Applied Mathematics 129, 195-209 2003. (pdf)




2002



R. Baeza-Yates, U. Montanari, N. Santoro (Eds),

FOUNDATIONS OF INFORMATION TECHNOLOGY IN THE ERA OF NETWORK AND MOBILE COMPUTING

Kluwer 2002.


E. Lodi, L. Pagli, N. Santoro (Eds),

Special Issue on Fun with Algorithms

Theoretical Computer Science 2002.


S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro,
Searching for a black hole in arbitrary networks: optimal mobile agent protocols
Proc. 21st ACM Symposium on Principles of Distributed Computing (PODC'02), 2002.
Extended version (pdf)


L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro,
Capture of an intruder by mobile agents
Symposium on Parallel Algorithms and Architectures (SPAA'02), 2002. (ps)


S. Dobrev, P. Flocchini, R. Kralovic, G. Prencipe, P. Ruzika, N Santoro,
Black hole search by mobile agents in hypercubes and related networks
Proc. 6th International Conference on Principles of Distributed Systems (OPODIS'02), 2002.
Extended version (pdf)


P. Flocchini, R. Kralovic, A. Roncato, P. Ruzicka, N. Santoro,
On time versus size for monotone dynamic monopolies in regular topologies
Journal of Discrete Algorithms 2: 2, 135-156, 2002. (pdf)




2001



E. Lodi, L. Pagli, N. Santoro (Eds),

FUN WITH ALGORITHMS (II)

Carleton Scientific 2001.


P. Flocchini, F. Geurts, N. Santoro,
Irreversible dynamos in chordal rings
Discrete Applied Mathematics 113, 23-42, 2001. (pdf)


E. Kranakis, N. Santoro,
Distributed computing on oriented anonymous hypercubes with faulty components
Distributed Computing, 14, 185-189, 2001. (pdf)


S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro,
Mobile agents searching for a black hole in an anonymous ring
Proc. 15th International Symposium on Distributed Computing (DISC'01), 166-179, 2001.
Extended version (pdf)


N. Zeh, N. Santoro,
On finding maximum deadly sets for directed networks
Proc. 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'01), 351--366, 2001. (ps)


P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,
Gathering of asynchronous mobile robots with limited visibility
Proc. 18th International Symposium Theoretical Aspects of Computed Science (STACS'01), 247-258, 2001.
Extended version (pdf)


P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,
Pattern formation by anonymous robots without chirality
Proc. 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'01), 147-162, 2001.
Extended version (pdf)


E. Velazquez, N. Santoro, A. Nayak,
A mobile agent prototype for distributed search
Proc. 3rd Int. Workshop on Mobile Agents for Telecommunications Applications, 2001.


E. Velazquez, N. Santoro, A. Nayak,
Distributed search using mobile agents
Proc. Int. Conf. on Intelligent Agents, Web Technologies and Internet Commerce, 2001.




2000



P. Flocchini, F. Geurts, A. Mingarelli, N. Santoro,
Convergence and aperiodicity in fuzzy cellular automata: revisiting rule 90
Physica D, 142, 20-28, 2000. (pdf)


A. Nayak, J. Ren, N. Santoro,
An improved testing scheme for catastrophic fault patterns
Information Processing Letters, 73, 199-206, 2000. (pdf)


P. Flocchini, R. Kralovic, A. Roncato, P. Ruzicka, N. Santoro,
On time versus size for monotone dynamic monopolies in regular topologies
Proc. 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO '00), 111-126, 2000.
Extended version (pdf)


U.-M. O'Reilly, N. Santoro,
Asynchronous to synchronous transformations
4th International Conference on Principles of Distributed Systems (OPODIS'00), 2000.


P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,
Limits to pattern formation by autonomous mobile robots
Proc. 3rd International Conference on Complex Systems (ICCS'00), 2000.


P. Flocchini, E. Kranakis, D. Krizanc, F.L. Luccio, N. Santoro,
Sorting multisets in anonymous rings
Proc. Int. Parallel and Distributed Processing Symposium (IPDPS'00), 2000. (pdf)


G. Coucopoulos, A. Nayak, N. Santoro,
On maintaining continuously K- tolerant distribution of ordered data
Proc. Int. Conf. on Communications and Computing, 93-199, 2000.


G. Coucopoulos, A. Nayak, N. Santoro,
Dynamic maintenace of full availability in distributed file systems
Proc. 1st Symp. on Advanced Distributed Systems, 2000.



1999


Y. Breitbart, S.K. Das, N. Santoro, P. Widmayer (Eds),

DISTRIBUTED DATA AND STRUCTURES 2

Carleton Scientific 1999.


P. Flocchini, A. Roncato, N. Santoro,
Biconsistency and homonymy in distributed systems with edge symmetry
Proc. 3rd International Conf. on Principles of Distributed Systems (OPODIS'99), 29-48, 1999.


P. Flocchini, F. Geurts, N. Santoro,
Irreversible dynamos in chordal rings
Proc. 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), 202-214,1999.
Extended version (pdf)


P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,
Hard tasks for weak robots
Proc. 10th International Symposium on Algorithm and Computation (ISAAC'99), 93-102, 1999. Extended version (pdf)


P. Flocchini, , E. Lodi, F. Luccio, L. Pagli, N. Santoro,
Monotone dynamos in tori
Proc. 10th 6th Colloquium on Structural Information and Communication Complexity (SIROCCO'99), 152-165, 1999. Extended version (ps)


P. Flocchini, A. Roncato, N. Santoro,
Backward consistency and sense of direction in advanced distributed systems
Proc. 18th ACM Symposium on Principles of Distributed Computing (PODC'99), 189-198, 1999.



1998


N. Santoro, P. Widmayer (Eds),

DISTRIBUTED DATA AND STRUCTURES

Carleton Scientific 1998.


E. Lodi, L. Pagli, N. Santoro (Eds),

FUN WITH ALGORITHMS

Carleton Scientific 1998.


P. Flocchini, A. Roncato, N. Santoro,
Symmetries and sense of direction in labeled graphs
Discrete Applied Mathematics, 99-115,1998. (pdf)


P. Flocchini, N. Santoro,
Topological constraints for sense of direction
Int. J. Foundations of Computer Science, 9, No. 2, 179-198, 1998.


P. Flocchini, B. Mans, N. Santoro,
Sense of direction: definitions, properties, and classes
Networks , 32, No. 3, 165-180, 1998.


B. Mans, N. Santoro,
Optimal elections in faulty loop networks and applications
IEEE Transactions on Computers , 47, No. 3, 286-297, 1998. (pdf)


E. Feuerstein, S. Leonardi, A. Marchetti-Spaccamela, N. Santoro,
Efficient token-based control in rings
Information Processing Letters , 66, 175-180, 1998. (pdf)


P. Flocchini, F. Geurts, A. Mingarelli, N. Santoro,
Convergence and aperiodicity in continous CA: revisiting Rule 90
Proc. Int. Conference on Complex Systems (Complex'98), 1998.


P. Flocchini, B. Mans, N. Santoro,
Sense of direction in distributed computing (invited paper)
Proc. International Symposium on Distributed Computing (DISC'98), 1-15, 1998.


P. Flocchini, E. Lodi, F. Luccio, L. Pagli, N. Santoro,
Irreversible dynamos in tori
Proc. EUROPAR 98, 554-562, 1998.



1997


M. Overmars, N. Santoro,
Improved bounds for electing a leader in a synchronous ring
Algorithmica , 18, 246-262, 1997.


P. Flocchini, F. Geurts, N. Santoro,
CA-like error propagation in fuzzy CA
Parallel Computing, 23, No. 11, 1673-1682, 1997. (pdf)


A. Negro, N. Santoro, J. Urrutia,
Efficient distributed selection with bounded messages
IEEE Transactions on Parallel and Distributed Systems,8, 397-401, 1997. (pdf)


P. Flocchini, B. Mans, N. Santoro
On the impact of sense of direction on message complexity
Information Processing Letters, 63, 23-31, 1997. (pdf)


G.Cattaneo, P.Flocchini, G.Mauri, C. Quaranta-Vogliotti, N.Santoro,
Cellular automata in fuzzy backgrounds
Physica D,105, 105-120, 1997. (pdf)


A. Israeli, E. Kranakis, D. Krizanc, N. Santoro,
Time-Messages tradeoffs for the weak unison problem
Nordic Journal of Computing,4, 317-329, 1997. (pdf)


E. Caceres, F. Dehne, A. Ferreira, P. Flocchini, I. Rieping, A. Roncato, N. Santoro, A.W. Song,
Efficient Parallel Graph Algorithms for Coarse Grained Multicomputers and BSP
Proc. Int. Colloqium on Automata, Languages, and Programming (ICALP'97), 390-400, 1997. (ps)


P. Flocchini, B. Mans, A. Roncato, N. Santoro,
Levels of sense of direction in distributed systems
Proc. 1st International Conference on Principles of Distributed Systems (OPODIS'97), 319-331,1997.



1996


N. Santoro, P. Spirakis (Eds),

STRUCTURE, INFORMATION AND COMMUNICATION COMPLEXITY 3

Carleton University Press 1996.


P. Alimonti, P. Flocchini, N. Santoro,
Finding the extrema of a distributed multiset of values
Journal of Parallel and Distributed Computing, 37, 123-133, 1996. (pdf)


A. Nayak, L. Pagli and N. Santoro,
On testing of catastrophic faults in reconfigurable arrays with arbitrary link redundancy
INTEGRATION: The VLSI Journal, 20, 327-342, 1996. (pdf)


J.L. Houle, N. Santoro,
Analysis of human Intereferon-alpha gene promoters by multiple sequence alignment
Journal of Interferon and Cytokine Research, 16, 93-98, 1996.


P. Flocchini, N. Santoro,
The chaotic evolution of information in the interaction between knowledge and uncertainty
Complexity International, 2, 1996.


P. Flocchini, A. Roncato, N. Santoro,
Complete symmetries and minimal sense of direction in labeled graphs
Proc. 27th SE Conference on Combinatorics, Graph Theory and Computing, 3-18, 1996.


A. Nayak, N. Santoro and Q. Xue,
Ring reconfiguration in presence of close fault cuts
Proc. International Symp. on Parallel Architectures, Algorithms and Networks, 422-428, 1996.
(pdf)


1995


S. Akl, F. Dehne, J. Sack, N. Santoro (Eds),

ALGORITHMS AND DATA STRUCTURES 4

Springer Verlag 1995.


A. Nayak, N. Santoro,
Reliability analysis of chordal rings
Journal of Circuits, Systems and Computers, 5, No. 2, 199-213, 1995.


P. Flocchini, B. Mans, N. Santoro,
Sense of direction, associativity, and symmetricity in distributed systems
26th SE Conference on Combinatorics, Graph Theory and Computing, 49-63, 1995.


P. Flocchini, F. Geurts, N. Santoro,
Dynamics and algebraic properties of reinforced shifts
International Symposium on Nonlinear Theory and Its Applications (NOLTA'95), 1149--1152, 1995.


P. Flocchini, B. Mans, N. Santoro,
Translation properties of sense of direction
2nd Colloquium on Structural Information and Communication Complexity (SIROCCO'95), 4-21, 1995.


P. Flocchini, N. Santoro,
Topological constraints for sense of direction
2nd Colloquium on Structural Information and Communication Complexity (SIROCCO'95), 22-37, 1995.


N. Santoro, J. Ren, A. Nayak,
On the complexity of testing for catastrophic faults
6th Int'l Symp. on Algorithms and Computation (ISAAC'95), 88-197, 1995.
Extended journal version (pdf)


A. Nayak, N. Santoro and Q. Xue,
Efficient reconfiguration technique for redundant ring networks
28th Hawaii Int. Conference on System Sciences, 489-498, 1995. (pdf)



1994


P. Flocchini, B. Mans, N. Santoro (Eds),

STRUCTURE, INFORMATION AND COMMUNICATION COMPLEXITY

Carleton University Press 1994.


H. Bodlaender, G. Tel, N. Santoro,
Tradeoffs for non reversing diameter
Nordic Journal of Computing, 1, 1994. (ps)


J. Czyzowicz, E. Rivera-Campo, N. Santoro, J. Urrutia, J. Zaks,
Guarding rectangular art galleries
Discrete Mathematics, 50, 149-157, 1994.


B. Mans, N. Santoro,
On the impact of sense of direction in arbitrary networks
14th IEEE Int. Conf. on Distributed Computing Systems (ICDCS'94), 258-265, 1994.


B. Mans, N. Santoro,
Optimal fault-tolerant elections in chordal rings
24th International Symposium on Fault-Tolerant Computing (FTCS'94), 392-401, 1994.


A. Israeli, E. Kranakis, D. Krizanc, N. Santoro,
Time-messages tradeoffs for the weak unison problem
International Conference on Algorithms and Complexity (CIAC'94), 1994.


N. Santoro, J. Ren, A. Nayak,
On the complexity of testing for catastrophic faults
6th Int'l Symp. on Algorithms and Computation (ISAAC'95), 88-197, 1995.


P. Flocchini, B. Mans, N. Santoro,
Distributed traversal and broadcasting in arbitrary networks with distance sense of direction
9th International Symposium on System Sciences,128-142, 1994.


P. Alimonti, P. Flocchini, N. Santoro
Finding the extrema of a distributed multiset of values
8th Int. Workshop on Distributed Algorithms (WDAG'94), 64--178, 1994.


G. Cattaneo, P. Flocchini, G. Mauri, C. Quaranta-Vogliotti, N. Santoro,
Chaos and complex dynamics in "fuzzy" cellular automata
Automi Cellulari per la Ricerca e per l'Industria (ACRI'94), 19-26, 1994.


P. Flocchini, N. Santoro,
The chaotic evolution of information in the interaction between knowledge and uncertainty
2nd Conference on Complex Systems, 337-344, 1994.


P. Flocchini, B. Mans, N. Santoro,
Sense of direction: formal definitions and properties
1st Colloquium on Structural Information and Communication Complexity (SIROCCO'94), 9-33, 1994.



1993


F. Dehne, J. Sack, N. Santoro, S. Whitesides (Eds),

ALGORITHMS AND DATA STRUCTURES 3

Springer Verlag 1993.


A. Nayak, L. Pagli and N. Santoro,
Efficient construction of catastrophic patterns for VLSI reconfigurable arrays
INTEGRATION: The VLSI Journal, 15, No. 2, 1993, 133-150.


G. Cattaneo, P. Flocchini, G. Mauri, N. Santoro,
Chaos and subshift rules in neural networks and cellular automata
International Symposium on Nonlinear Theory and Its Applications (NOLTA'93), 1153--1156, 1993.


G. Cattaneo, P. Flocchini, G. Mauri, N. Santoro,
A new classification of cellular automata and their algebraic properties
International Symposium on Nonlinear Theory and Its Applications (NOLTA'93), 223--226, 1993.


G. Cattaneo, P. Flocchini, G. Mauri, N. Santoro,
Fuzzy cellular automata and their chaotic behavior
International Symposium on Nonlinear Theory and Its Applications (NOLTA'93), 1285--1289, 1993.



1992


N. Santoro, J.B. Sidney, S.J. Sidney,
A distributed selection algorithm and its expected communication complexity
Theoretical Computer Science, 100, 185-204, 1992.


A. Nayak, L. Pagli, N. Santoro,
Recognition of catastrophic faults
4th IEEE Int. Workshop on Defect and Fault Tolerance, 70-79, 1992. (pdf)


E. Kranakis, N. Santoro,
Distributed computing on anonymous hypercubes with faulty components
5th Int. Workshop on Distributed Algorithms (WDAG'92), LNCS 657, 321-332, 1992.


A. Nayak, L. Pagli, N. Santoro,
Combinatorial and graph problems arising in the analysis of catastrophic fault patterns
Proc. 24th SE Conf. on Combinatorics, Graph Theory and Computing, 7-20, 1992.


A. Nayak, L. Pagli, N. Santoro,
Efficient construction of catastrophic patterns for VLSI reconfigurable arrays with bidirectional links
Proc. 4th IEEE Int. Conf. on Computing and Information, 79-83, 1992. (pdf)


A. Nayak, N. Santoro,
Performance analysis of redundant ring networks
Proc. Int. Conf. on Parallel Computing, 331-322, 1992.


A. Nayak, N. Santoro,
Limits to reconfigurability of loop topologies
Proc. Int. Symp. on Parallel and Distributed Computing in Engineering Systems, 453-458, 1992.


U.M. O'Reilly, N. Santoro
The expressiveness of silence: optimal algorithms for synchronous communication of information
Proc. 18th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG'92), LNCS 657, 321-332, 1992.



1991


F. Dehne, J. Sack, N. Santoro (Eds),

ALGORITHMS AND DATA STRUCTURES 2

Springer Verlag 1991.


F. Dehne, A.-L. Hassenklover, J. Sack, N. Santoro,
Computational geometry algorithms for the systolic screen
Algorithmica , 6, 734-761, 1991.


J. Czyzowicz, E. Rivera-Campo, N. Santoro, J. Urrutia, J. Zaks,
Tight bounds for the rectangular art gallery problem
Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG'91), 1991.


A. Nayak, N. Santoro,
Bounds on performance of VLSI processor arrays
Proc. 5th Int. Parallel Processing Symposium, 453-458, 1991.


R.B. Black, N. Santoro,
Visualization techniques for fully discrete dynamical systems
Proc. Int. Workshop on Chaos and Evolution in Cognitive Processing, 1-16, 1991.


A. Nayak, N. Santoro,
Fault-tolerance analysis of some regular networks
Proc. Int. Conf. on Parallel Computing, 67-76, 1991.



1990


J. van Leeuwen, N. Santoro (Eds),

DISTRIBUTED ALGORITHMS

Springer Verlag 1990.


M.D. Atkinson, A. Negro, N. Santoro,
Sums of lexicographically ordered sets
Discrete Mathematics, 80, 115-122, 1990.


N. Santoro,
Computing with time: Temporal dimensions in distributed computing (invited paper)
Proc. Allerton Conf. on Communication, Control and Computing, 558-567, 1990.


N. Santoro, P. Widmayer,
Distributed function evaluation in presence of transmission faults
Proc. Int. Symp. on Algorithms (SIGAL'90), LNCS 450, 358-367, 1990.


A. Nayak, N. Santoro, R.B. Tan,
Fault intolerance of reconfigurable systolic arrays
Proc. 20th Int. Symp. on Fault-Tolerant Computing (FTCS'90) , 202-209, 1990. (pdf)



1989


F. Dehne, J. Sack, N. Santoro (Eds),

ALGORITHMS AND DATA STRUCTURES

Springer Verlag 1989.


N. Santoro, E. Suen,
Reduction techniques for selection in a distributed file
IEEE Transactions on Computers, 38, 6, 891-896, 1989. (pdf)


N. Santoro, J.B. Sidney, S.J. Sidney, J. Urrutia,
Geometric containment and partial orders
SIAM J. Discrete Mathematics
, 2, 2, 245-254, 1989. (pdf)


H. Attiya, J. vanLeeuwen, N. Santoro, S. Zaks,
Efficient elections in chordal ring networks
Algorithmica
, 4, 437-446, 1989.


N. Santoro, P. Widmayer,
Time is not a healer
Proc. 6th Symp. on Theoretical Aspects of Computer Science (STACS)
, LNCS 349, 304-313, 1989. (pdf)


M. Overmars, N. Santoro,
Time vs Bits
Proc. 6th Symp. on Theoretical Aspects of Computer Science (STACS)
, LNCS 349, 282-293, 1989.


F. Dehne, N. Santoro,
An improved embedding for VLSI dictionary machines on meshes
Proc. Int. Symp. on Computer Applications , 113-116, 1989.


V. Acciaro, A. Nayak, N. Santoro,
On the fault-tolerance of reconfigurable VLSI systolic arrays
18th Conf. on Numerical Mathematics and Computing, 197-210, 1989.


F. Dehne, N. Santoro,
Optimal VLSI dictionary machines for hypercube architectures
Int. Workshop on Parallel and Distributed Algorithms , 137-144, 1990.



1988


N. Santoro, M. Scheutzow, J.B. Sidney,
On the expected complexity of distributed selection
J. of Parallel and Distributed Computing, 5, 194-203, 1988.


M.D. Atkinson, N. Santoro,
A practical algorithm for Boolean matrix multiplication
Information Processing Letters, LNCS 334, 180-189, 1988.


N. Santoro,
Time*space efficient implementations of hierarchical conceptual models
Proc. 14th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG'89), 29, 37-38, 1988.


A. Nayak, N. Santoro,
Scatter: A distributed file system with decentralized control
Proc. Conf. on Parallel Processing Systems and their Applications, 241-246, 1988.



1987


E. Korach, D. Rotem, N. Santoro,
Analysis of a distributed algorithm for extema finding in a ring
J. of Parallel and Distributed Computing, 4, 457-591, 1987.


S. Akl, N. Santoro,
Optimal parallel merging without memory conflicts
IEEE Transactions on Computers, 36, 11, 1367-1369, 1987.


N. Santoro, J. Urrutia,
Angle orders, regular n-gon orders and crossing numbers
Order, 4, 209-220, 1987. (pdf)


J.B. Sidney, S.J. Sidney, J. Urrutia,
Geometric containment and vector dominance
Theoretical Computer Science, 53, 345-352, 1987.


J. van Leeuwen, N. Santoro, J. Urrutia, S. Zaks,
Guessing games and distributed computations in synchronous networks
Proc. 14th Int. Coll. on Automata, Languages and Programming (ICALP'87), LNCS 267, 347-356, 1987. (pdf)


H. Attiya, N. Santoro, S. Zaks
From rings to complete networks: O(n logn) to O(n) distributed elections
Proc. 2nd Symp. on Cooperation, Concurrency and Communication, 19-26, 1987.


N. Santoro, J.B. Sidney, S.J. Sidney,
On the expected communication complexity of distributed selection
4th Symp. on Theoretical Aspects of Computer Science (STACS'87), LNCS 247, 456-467, 1987.


A. Negro, N. Santoro, J. Urrutia,
On the packet complexity of distributed selection
Proc. 2nd Int. Workshop on Distributed Algorithms (DISC'87), LNCS 312, 108-115, 1987.


G.N. Frederickson, N. Santoro,
Symmetry breaking in synchronous networks
2nd Aegean. Workshop on Parallel Computing and VLSI (SPAA'87), LNCS 227, 26-33, 1987.


E. Otoo, N. Santoro, D. Rotem,
Improving semijoin evaluation in distributed query processing
Proc. 7th IEEE Int. Conf. on Distributed Computing Systems (ICDCS'87), 554-561, 1987.


F. Dehne, J. Sack, N. Santoro,
Parallel visibility on a mesh-connected parallel computer
Proc. Int. Conf. on Parallel Processing and Applications, 173-180, 1987.


F. Dehne, N. Santoro,
Optimal VLSI dictionary machines on meshes
Proc. 16th Int. Conf. on Parallel Processing, 830-840, 1987.


F. Dehne, J. Sack, N. Santoro,
Computing on a systolic screen: covex hulls and applications
Proc. Conf. on Parallel Languages and Architectures, LNCS 258, 121-133, 1987.



1986


D. Rotem, N. Santoro, J.B. Sidney,
Shout-echo selection in distributed files
Networks , 16, 77-86, 1986.


N. Santoro, J. Urrutia,
An improved algorithm for Boolean matrix multiplication
Computing, 36, 375-382, 1986.


V. Neumann-Lara, N. Santoro, J. Urrutia,
Uniquely colourable m-dichromatic oriented graphs
Discrete Mathematics, 62, 65-70, 1986.


M.D. Atkinson, J. Sack, N. Santoro, Th. Strothotte,
Min-max heaps and generalized priority queues
Communications of the ACM, 29, 10, 996-1000. , 1986. (pdf)


M.D. Atkinson, N. Santoro, J. Urrutia,
Integer sets with distinct sums and differences and carrier frequency assignment for non-linear repeaters
IEEE Transactions on Communications, 34, 6, 614-617, 1986. (pdf)


M.D. Atkinson, N. Santoro, J. Urrutia,
On the integer complexity of Boolean matrix multiplication
SIGACT News , 18, 1, 53-56, 1986. (pdf)


N. Santoro, E. Suen,
Reduction techniques for selection in a distributed file
Proc. 15th Int. Conf. on Parallel Processing, 38, 6, 1003-1009, 1986.



1985


E. Gafni, N. Santoro (Eds),

DISTRIBUTED ALGORITHMS ON GRAPHS

Carleton University Press 1985.


D. Rotem, N. Santoro, J.B. Sidney,
Distributed sorting
IEEE Transactions on Computers, 34, 4, 372-376, 1985.


N. Santoro, R. Khatib,
Labelling and implicit routing in networks
The Computer Journal, 29, 1, 5-8, 1985.


N. Santoro, J.B. Sidney,
Interpolation-binary search
Information Processing Letters, 20, 179-181, 1985.


N. Santoro,
The un-merging problem
SIGACT News, 17, 1, 5-6, 1985. (pdf)


N. Santoro, J.B. Sidney, S.J. Sidney, J. Urrutia,
Geometric containment is not reducible to Pareto dominance
Proc. 2nd Symp. on Theoretical Aspects of Computer Science (STACS'85), LNCS , 26-33, 1985.


N. Santoro, J. Urrutia, S. Zaks,
Sense of direction and communication complexity in distributed networks
1st Int. Workshop on Distributed Algorithms (WDAG'85), 123-132, 1985. (pdf)


N. Santoro, D. Rotem,
Communication complexity of distributed elections in synchronous graphs
11th Workshop on Graphtheoretic Concepts in Computer Science (WG'85), 337-346, 1985.


D. Rotem, N. Santoro,
Distributed algorithms on graphs (invited paper)
8th IEEE Int. Symp. on Circuits and Systems, 1985.


S. Akl, N. Santoro,
Optimal parallel merging without memory conflicts
Proc. 1st Int. Conf. on Supercomputing Systems, 205-208, 1985.


M.D. Atkinson, J. Sack, N. Santoro, T. Strothotte,
Min-max-heaps, order-statistics-trees and their application to the Course Marks problem
Conf. on Information Sciences and Systems, 1985.



1984


E. Korach, D. Rotem, N. Santoro,
Distributed algorithms for finding centers and medians in networks
ACM Transactions on Programming Languages and Systems, 6, 3, 380-401, 1984. (pdf)


N. Santoro,
On the message complexity of distributed problems
nt. Journal of Computer and Information Sciences, 13, 3, 131-147, 1984.


E. Korach, D. Rotem, N. Santoro,
Distributed election in a circle without a global sense of orientation
Int. Journal of Computer Mathematics,16, 115-124.


N. Santoro,
Chain multiplication of matrices of almost or exactly the same size
Communications of the ACM, 27, 4, 152-156, 1984. (pdf)


N. Santoro,
Sense of direction, topological awareness and communication complexity
SIGACT News, 16, 2, 50-56, 1984. (pdf)


J. Sack, N. Santoro, J. Urrutia,
Containment of elementary geometric objects
Proc. 15th SE Conf. on Combinatorics, Graph Theory and Computing, 139-146, 1984.


J.P. Corriveau, N. Santoro,
SADE: an environment for the design of systolic algorithms
Proc. Conf. on Computer-Aided Design, 1984.



1983


D. Rotem, N. Santoro, J.B. Sidney,
A shout-echo algorithm for finding the median of a distributed set
Proc. 14th SE Conf. on Combinatorics, Graph Theory and Computing, 311-318, 1983.


P. Piche, M. Krieger, N. Santoro,
Oligarchy: a control scheme for flexible manufacturing systems
Proc. 2nd Conf. on Robotics and Automation, 35-39, 1983.


1982


M. Krieger, N. Santoro,
Open questions in complex computer systems design
Proc. Int. Conf. on Advances in Information Sciences, 115-121, 1982.


N. Santoro, J.B. Sidney,
Order statistics on distributed sets
Proc. 20th Allerton Conf. on Communication, Control and Computing, 251-256, 1982.


M. Krieger, N. Santoro,
Oligarchical control of distributed processing systems
Proc. 20th Allerton Conf. on Communication, Control and Computing, 793-802, 1982.


N. Santoro, H. Ural,
Concurrency control in large computer networks
Proc. IEEE Int. Symp. on Large Scale Systems, 272-276, 1982.


E. Korach, D.Rotem, N. Santoro,
Distributed algorithms for ranking the nodes of a network
Proc. 13th SE Conf. on Combinatorics, Graph Theory and Computing, 235-246, 1982.


1981


N. Santoro, R. Khatib,
Labelling and addressing in distributed systems
Proc. 19th Allerton Conf. on Communication, Control and Computing, 195-203, 1981.


N. Santoro,
Distributed algorithms for very large distributed environments: new results and research directions
Proc. Canadian Information Processing Society Annual Conf. (CIPS'81), 141-145, 1981.


N. Santoro, R.L. Probert,
Designing efficient parallel algorithms for multiple-output computations with fan-in constraints
Proc. 19th Allerton Conf. on Communication, Control and Computing, 204-210, 1981.


N. Santoro,
Four O(n**2) multiplication methods for sparse and dense Boolean matrices
Proc. 10th Conf. on Numerical Mathematics and Computing, 241-252, 1981.


1980


N. Santoro,
Extending the four Russians' bound to general matrix multiplication
Information Processing Letters, 10, 2, 87-88. , 1980.


N. Santoro,
Determining topology information in distributed systems
Proc. 11th Southeastern Conf. on Combinatorics, Graph Theory and Computing
, 869-878, 1980.


N. Santoro,
A discrete polynomial transform and its applications
Proc. Conf. on Discrete Mathematical Analysis and Combinatorial Computations
, 40-60, 1980.


1970s


N. Santoro,
EFFICIENT ABSTRACT IMPLEMENTATIONS FOR RELATIONAL DATA STRUCTURES
Ph.D. Thesis
, Department of Computer Science, University of Waterloo, 1979. (pdf)


F. Romani, N. Santoro,
On hash techniques in a paged environment
Calcolo
, 16, 3, 298-303, 1979.


R.J. Ramirez, N. Santoro,
Distributed control of updates in multiple-copy databases: a time optimal algorithm
Proc. 4th Berkeley Conf. on Distributed Data Management and Computer Networks, 191-206, 1979.


N. Santoro,
On the parallel evaluation of general arithmetic expressions
Proc. 9th Conf. on Numerical Mathematics and Computing, 195-203, 1979.


N. Santoro,
On the topological design of computer communication networks
Proc. IEEE Int. Conf. on Computers, Electronics and Control, 122-123, 1978.


N. Santoro,
Economic handling of constraints in picture processing
Proc. IEEE Conf. on Picture Data Description and Management, 93-95, 1977.


N. Santoro,
Conditions for the efficiency of generalized parking functions
Proc. 7th Conf. on Numerical Mathematics and Computing, 532-542, 1976.


E. Lodi, F. Luccio, L. Pagli, N. Santoro,
Random access in a list environment
Information Systems, 2, 11-17, 1976.


N. Santoro,
Full table search by polynomial functions
Information Processing Letters, 5, 3, 72-74., 1976.


N. Santoro,
Operations on permutations and representation in graph form
Calcolo , 13, 2), 123-129, 1976.


E. Lodi, F. Luccio, L. Pagli, N. Santoro,
Problemi di partizione e ricerca su strutture informative
Proc. Convegno di Informatica Teorica, 1974.